[Swift] 백준 1261 - 알고스팟

문제 바로가기 👉🏻

풀이

(1,1)에서 (N,M)까지 이동하면서 벽을 가장 적게 부수는 경우를 알아내야한다.

여태까지는 BFS를 이용해서 최단 거리를 구하곤 했었는데,
이번엔 거리는 상관이 없고 그저 벽을 가장 적게 부수기만 하면 된다!

처음엔 방문해야하는 위치를 저장하는 queue needToVisit에
튜플로 위치와 만난 벽의 수도 함께 저장하였다 => (x,y,벽의 수)
그리고 check 배열을 사용해서 방문여부를 저장하였다.

그러나, 이렇게 하게되면
같은 회차의 needToVisit에 담긴 방문해야하는 위치 중, 부수는 벽의 수가 더 많은 위치가 (N,M)에 먼저 방문하게 되면 벽의 수가 더 적은 위치는 고려될 수 없는 문제가 생긴다.

그래서 알고리즘을 어떻게 짜든지 간에 가장 중요한 건,
방문한 위치여도 재방문할 수 있도록 해야하는 것이다.
그러나, 그렇다고 해서 또 모든 위치에 재방문 할 수 있는건 아니다.
그렇게 되면 이 반복문이 무한으로 돌게 되기 때문이다.

따라서, 이를 해결하기 위해
해당 위치의 벽의 수를 저장하는 counts 배열을 사용하였다.
var counts = Array(repeating: Array(repeating: Int.max, count: 101), count: 101)

1을 만났을 때
만약 (이동할 위치의 counts 배열 값) > (기존 위치의 counts 배열 값 + 1) 이라면
이동할 위치의 counts 배열 값에 기존 위치의 counts 배열 값 + 1 을 넣고
needToVisit에 해당 위치를 추가해준다.

왜냐하면

• (이동할 위치의 counts 배열 값) > (기존 위치의 counts 배열 값 + 1) 이라면
  • 값이 Int.max 여서 아직 방문하지 않았거나
  • 이미 방문했던 값이 벽을 더 많이 부순 경우

이기 때문에 벽의 수를 갱신해야하고 needToVisit에 이동 할 위치를 추가해준다.

• (이동할 위치의 counts 배열 값) < (기존 위치의 counts 배열 값 + 1)
  • 지금 방문하려는 값이 벽을 더 많이 부수는 경우

이기 때문에 방문할 필요가 없고, needToVisit에 해당 위치를 추가할 필요가 없다.

=> 이렇게 counts 배열을 사용하면 방문 여부를 알 수 있고, 조건에 따른 재방문을 허용할 수도 있다.

Swift 코드

import Foundation

let location = readLine()!.split(separator: " ").map {Int(String($0))!}

let N = location[0] - 1
let M = location[1] - 1

var graph = [[Int]]()
var needToVisit = [(Int,Int)]()
var counts = Array(repeating: Array(repeating: Int.max, count: 101), count: 101)

for _ in 0...M {
    let arr = Array(readLine()!).map{Int(String($0))!}
    graph.append(arr)
}

func bfs(row: Int, col: Int) {
    needToVisit.append((row,col))
    counts[row][col] = 0
    
    while !needToVisit.isEmpty {
        let node = needToVisit.removeFirst()
        for i in [(-1,0),(0,1), (0,-1),(1,0)] {
            let nx = node.0 + i.0
            let ny = node.1 + i.1
            
            if 0...M ~= nx && 0...N ~= ny {
                if graph[nx][ny] == 1 {
                    if counts[nx][ny] > counts[node.0][node.1] + 1{
                        counts[nx][ny] = counts[node.0][node.1] + 1
                        needToVisit.append((nx,ny))
                    }
                    
                } else if graph[nx][ny] == 0 {
                    if counts[nx][ny] > counts[node.0][node.1] {
                        counts[nx][ny] = counts[node.0][node.1]
                        needToVisit.append((nx,ny))
                    }
                }
            }
        }
    }
}

bfs(row: 0, col: 0)
print(counts[M][N])

• 문제에서 시작하는 위치를 (1,1)로 두었지만 나는 (0,0)에서 시작하고자 하였기에 N과 M에 각각 -1을 해주었다.