[Swift 백준] 1303 전쟁 - 전투

https://www.acmicpc.net/problem/1303

 

풀이 아이디어

그래프 탐색문제입니다.

적군과 아군의 경우 모두 조사해야합니다.

매번 bfs로 탐색하여 결과값의 제곱만큼 += 해주어 결과를 출력합니다.

자세한 풀이는 아래와 같습니다.

 

풀이

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (m, n) = (nm[0], nm[1])

let dn = [0, 0, -1, 1]
let dm = [-1, 1, 0, 0]

var graph = [[String]]()
var isVisited = Array(repeating: Array(repeating: false, count: m), count: n)

var whiteCount = 0
var blueCount = 0

for _ in 0..<n {
    let input = readLine()!.map { String($0) }
    graph.append(input)
}

// 어떤 팀의 그래프 탐색인지를 파라미터로 받았습니다.
func bfs(startN: Int, startM: Int, team: String) -> Int {
    var queue = [[startN, startM]]
    //첫방문 체크
    isVisited[startN][startM] = true
    // 1부터 시작
    var count = 1
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        let currentN = current[0]
        let currentM = current[1]
        
        for i in 0..<4 {
            let nextN = currentN + dn[i]
            let nextM = currentM + dm[i]
            
            if nextN >= 0, nextN < n, nextM >= 0, nextM < m {
            // 내 팀과 같으면 진행하여 count += 1
                if !isVisited[nextN][nextM] && graph[nextN][nextM] == team {
                    queue.append([nextN, nextM])
                    isVisited[nextN][nextM] = true
                    count += 1
                }
            }
        }
    }
    return count
}

for i in 0..<n {
    for j in 0..<m {
        if !isVisited[i][j] {
            let team = graph[i][j]
            let count = bfs(startN: i, startM: j, team: team)
            // 아군과 적군의 경우 모두 수행, 제곱만큼 +=
            if team == "W" {
                whiteCount += count * count
            } else {
                blueCount += count * count
            }
        }
    }
}

print(whiteCount, blueCount)