백준 - 전쟁전투(Swift)

백준 - 전쟁전투(Swift)

 

 

 문제 설명

 

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

1303번: 전쟁 - 전투

 

 나의 풀이

 

간단했던 DFS, BFS문제였지만 큐에서 꺼내는 값을 var로 둠으로써 누적되지않을때도 누적되었기 때문에 시간이 조금 오래걸렸다.

그리고 뭉쳐있는 B와 W들의 개수를 구하는 것이 포인트였는데 BFS로 최단거리를 구하려고하는 판단오류가 있었다. 

그래서 BFS로 접근하려고 했다. (DFS든 BFS든 상관없지만 이 문제는 DFS적인 사고가 더 올바른 해답으로 보인다)

 

그리고 다른사람의 풀이를 보니 굳이 WBFS와 BBFS로 나누지 않고 BFS를 호출할때 G[i][j]값도 넘겨줌으로써 이전에 값과 같은 값에 대해서만 탐색할 수 있게 만들었다. 

 

import Foundation

let nm = readLine()!.components(separatedBy:" ").map{Int($0)!}
let dx = [-1, 0, 1, 0]
let dy = [0, -1, 0, 1]
let N = nm[1], M = nm[0]
let xRange = 0..<N
let yRange = 0..<M
var G = [[String]]()
var visited = Array(repeating: Array(repeating: false, count: M), count: N)
var distance = Array(repeating: Array(repeating: 0, count: M), count: N)
var blueCnt = 0
var whiteCnt = 0
for _ in 0..<N {
    G.append(readLine()!.map{String($0)})
}

func BFS(_ x: Int, _ y: Int) {
    if G[x][y] == "B" {
        BBFS(x, y)
    } else {
        WBFS(x, y)
    }
}

func BBFS(_ x: Int, _ y: Int) {
    var cnt = 1
    var index = 0
    var queue = [(Int, Int)]()
    var maxBlue = 1
    visited[x][y] = true
    queue.append((x, y))
    while index < queue.count {
        let curr = queue[index]
        let x = curr.0, y = curr.1
        index += 1
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            if xRange ~= nx, yRange ~= ny, !visited[nx][ny], G[nx][ny] == "B" {
                cnt += 1
                visited[nx][ny] = true
                queue.append((nx, ny))
            }
        }
    }
    blueCnt += (cnt * cnt)
}

func WBFS(_ x: Int, _ y: Int) {
    var cnt = 1
    var index = 0
    var queue = [(Int, Int)]()
    var maxWhite = 1
    visited[x][y] = true
    queue.append((x, y))
    while index < queue.count {
        let curr = queue[index]
        let x = curr.0, y = curr.1
        index += 1
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            if xRange ~= nx, yRange ~= ny {
                if G[nx][ny] == "W", !visited[nx][ny] {
                    cnt += 1
                    visited[nx][ny] = true
                    queue.append((nx, ny))
                }
                
            }
        }
    }
    whiteCnt += (cnt * cnt)
}

for i in 0..<N {
    for j in 0..<M {
        if !visited[i][j] {
            BFS(i, j)
        }
    }
}





print("\(whiteCnt) \(blueCnt)")

 

 다른 사람의 풀이

 

 

import Foundation

let nm = readLine()!.components(separatedBy:" ").map{Int($0)!}
let dx = [-1, 0, 1, 0]
let dy = [0, -1, 0, 1]
let N = nm[1], M = nm[0]
let xRange = 0..<N
let yRange = 0..<M
var G = [[String]]()
var visited = Array(repeating: Array(repeating: false, count: M), count: N)
var distance = Array(repeating: Array(repeating: 0, count: M), count: N)
var blueCnt = 0
var whiteCnt = 0
for _ in 0..<N {
    G.append(readLine()!.map{String($0)})
}

func BFS(_ x: Int, _ y: Int, _ c: String) {
    var cnt = 1
    var index = 0
    var queue = [(Int, Int)]()
    var maxWhite = 1
    visited[x][y] = true
    queue.append((x, y))
    while index < queue.count {
        let curr = queue[index]
        let x = curr.0, y = curr.1
        index += 1
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            if xRange ~= nx, yRange ~= ny {
                if G[nx][ny] == c, !visited[nx][ny] {
                    cnt += 1
                    visited[nx][ny] = true
                    queue.append((nx, ny))
                }   
            }
        }
    }
    if G[x][y] == "W" {
        whiteCnt += (cnt * cnt)
    } else {
        blueCnt += (cnt * cnt)
    }
}

for i in 0..<N {
    for j in 0..<M {
        if !visited[i][j] {
            BFS(i, j, G[i][j])
        }
    }
}


print("\(whiteCnt) \(blueCnt)")