[Swift][BFS] 백준 16946번 (벽 부수고 이동하기4)

요구능력 : BFS

 

코드설명 : 

 

https://go-coding.tistory.com/54

[백준 16946번] 벽 부수고 이동하기4(java)

 

위의 분 께서 설명을 너무 잘해주셔서 덕분에 문제를 쉽게 이해할 수 있었다.

 

이 문제는 벽이 있는 위치에서 현재 위치한곳의 벽을 부수고 그 벽을 부순 자리에서 몇번 이동이 가능한지를 묻는 문제이다.

가장 쉬운 방법은 1이 있는 위치에서 BFS를 돌리는건데, 그냥 그렇게만 하면 O(n * m)의 시간복잡도를 가지므로 최악의 경우에는 100만번의 BFS를 돌아야한다. 그럼 시간초과가 날것이다.

여기까지는 생각하기 쉬웠는데 그럼 대체 어떻게 해야할까.. 하다가 서칭을 해보고 위의 블로그를 보고 이해를 했다.

 

결론적으로 짧게 설명해보자면

0이 있는 위치에서 BFS를 돌리면서 연결된 0들은 다 그룹으로 묶어줌으로써 BFS를 도는 횟수도 줄게되고,

맵에서 1이 연결된 부분을 찾아서 더할때도 주변의 그룹만 찾아서 그룹의 크기를 중복되지 않게 더해주기만 하면된다.

 

참고로 출력시에 2중 for문을 사용하게되면 시간초과가 나오게된다.

String으로 바꿔서 한번에 출력하는게 훨씬 빠르다.

 

후기 : 문제를 보고 풀이방법을 생각하기 어려운 문제인 것 같다. 근데 왜 벽부수고 이동하기 2보다는 쉬운거같지.. 하하

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

var arr = [[Int]]()
for _ in 0..<n{
    arr.append(readLine()!.map{Int(String($0))!})
}

var groupArr = Array(repeating: Array(repeating: 0, count: m), count: n)
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
var insuvisited = Array(repeating: Array(repeating: false, count: m), count: n)
func bfs(_ startX: Int, _ startY: Int, _ cnt: Int, _ insuvisited: [[Bool]]) -> Int{
    var count = 0
    var queue = [(Int, Int)]()
    var visited = insuvisited
    queue.append((startX, startY))
    count += 1
    visited[startX][startY] = true
    groupArr[startX][startY] = cnt
    
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        let x = pop.0
        let y = pop.1
        
        for i in 0..<4{
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] {continue}
            if arr[nx][ny] == 1 {continue}
            queue.append((nx, ny))
            visited[nx][ny] = true
            groupArr[nx][ny] = cnt
            count += 1
        }
    }
    
    
    return count
}


var cnt = 0
var lengthArr = Array(repeating: 0, count: n * m + 1)
for i in 0..<n{
    for j in 0..<m{
        if arr[i][j] == 0{
            if groupArr[i][j] == 0 {
                cnt += 1
                lengthArr[cnt] = bfs(i, j, cnt, insuvisited)
            }
            
        }
    }
}

var resultArr = Array(repeating: Array(repeating: "0", count: m), count: n)
for i in 0..<n{
    for j in 0..<m{
        if arr[i][j] == 1{
            var around = Set<Int>()
            for k in 0..<4{
                let nx = i + dx[k]
                let ny = j + dy[k]
                
                if nx < 0 || nx >= n || ny < 0 || ny >= m || around.contains(groupArr[nx][ny]) {continue}
                around.insert(groupArr[nx][ny])
            }
            var sum = 1
            for v in around{
                sum += Int(resultArr[i][j])! + lengthArr[v]
                
            }
            resultArr[i][j] = String(sum % 10)
        }
    }
}
for i in resultArr{
    print(i.joined(separator: ""))
}