[Swift Algorithm] 벽 부수고 이동하기 BOJ #2206

문제

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

2206번: 벽 부수고 이동하기

 

내 문제 풀이

let nm = readLine()!.split(separator: " ").map({Int(String($0))!})
let n = nm[0]
let m = nm[1]
var map = [[Int]]()
var result = 0
var queue = [(Int, Int, Int)]()
let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0]
var visited = Array(repeating: Array(repeating: [0, 0], count: m), count: n)

for _ in 0..<n { map.append(Array(readLine()!).map{Int(String($0))!}) }

func bfs() -> Int {
    queue.append((0, 0, 1))
    visited[0][0][1] = 1
    var index = 0
    
    while queue.count > index {
        let (x, y, z) = queue[index]
        index += 1
        
        if (x, y) == (n-1, m-1) { return visited[x][y][z] }
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || ny < 0 || nx >= n || ny >= m { continue }
            
            if visited[nx][ny][z] == 0 {
                // 벽이고, 벽을 부수지 않았던 경우 => 부술 수 있는 경우
                if map[nx][ny] == 1 && z == 1 {
                    visited[nx][ny][0] = visited[x][y][1] + 1
                    queue.append((nx, ny, 0))
                }
                // 벽이 아닐 경우
                else if map[nx][ny] == 0 {
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    queue.append((nx, ny, z))
                }
            }
        }
    }
    
    return -1
}

print(bfs())

👉 bfs 문제로, 3차원 배열을 만들어서 자리마다 벽을 부쉈는지, 부수지 않고 이동했는지 체크해주는게 포인트,,!

이 문제는 경로를 탐색하면서, 벽을 부수고 왔는지 아니면 부수지 않고 왔는지를 함께 파악해주어야 하므로
2차원 배열에서 3차원 배열로 확장하여 (벽을 부수고 온 경우) / (부수지 않고 온 경우)로 나누어 체크해야한다.

 

[ 변수 설명 ]

• queue는 bfs 함수에서 탐색할 자리들을 누적하는 배열이다.
  (x좌표, y좌표, 부순 적 있는지(0)/부순 적 없는지(1)) 형태로 저장할 수 있게 했다.
• dx, dy는 탐색할 좌표를 만들기 위한 배열이다.
• visited는 자리마다 방문 여부를 체크하고, 해당 자리까지 걸린 시간을 저장하는 배열이다.
  3차원으로 확장해서 '부순 이력이 있는지 / 부순 적 없는지'까지 확인할 수 있게 했다.
  [x][y][0]에 0 이상의 값이 저장된다면 한 번 부순적 있는 상태로 (x, y)에 방문했다는 의미이고,
  [x][y][1]에 0 이상의 값이 저장된다면 부순 적은 없는 상태로 (x, y)에 방문했다는 뜻이다.

 

[ bfs 함수 설명 ]

• 가장 먼저 queue에 탐색을 시작할 자리에 대한 정보를 추가해주었다.
  시작점은 아직 벽을 부순 적 없는 것이 당연하므로 (0, 0, 1)을 추가했다.
• 그리고 (0, 0) 좌표를 방문했고 벽은 부수지 않았으므로
  visited[0][0][1]에 1을 저장해주었다. (1은 이동한 시간을 의미하는데, 문제에서 주어진 조건에 의한다.)
• index 변수를 사용하여 removeFirst를 피해주어 시간 복잡도를 줄였다.
• for문을 4번 반복하여 상하좌우에 대한 좌표값을 구해 탐색하도록 했고,
  탐색할 자리가 map의 범위를 벗어나지 않으며 방문한 적 없는 경우에 대해서 탐색을 진행했다.
• 탐색할 자리에 벽이 있을 경우, z가 1이어야만 벽을 부술 수 있다는 뜻이 된다.
  따라서 map[nx][ny] == 1 && z == 1 일 경우를 조건으로 빼주었다.
  이 때는 visited 배열에 해당 자리의 벽을 부쉈다는 것을 표시하고, 걸린 시간을 기록했다.
  그리고 queue에 새롭게 탐색할 좌표와, 벽을 부쉈다는 정보를 함께 추가해주었다.
• 벽이 없을 경우에는 z 값은 관계가 없으므로 생각해줄 필요가 없다.
  이 때는 벽이 있을 경우의 조건과 같이 여기까지 온 거리를 기록해주고,
  이전에 벽을 부쉈는지에 대한 이력은 그대로 전달해주었다.
  그리고 새롭게 탐색할 좌표와, 마찬가지로 이전에 벽을 부쉈는지에 대한 이력도 함께 추가했다.
• 가장 먼저 (n-1, m-1) 좌표에 도달한 경우가 가장 최단 시간에 도착한 경우가 되므로
  그 때는 해당 자리에 저장된 값을 리턴했다.
• while 반복이 진행되는 동안 한 번도 (n-1, m-1) 좌표에 도달하지 못했다면
  도달할 수 없었다는 의미이므로 그 때는 -1을 리턴하게 했다.

 

💡 피드백

• 3차원 배열을 만들어서 ( 벽을 부순 경우 / 부수지 않은 경우 ) 이렇게 나눠줄 생각을 할 수 있다면
  크게 어렵지 않은 문제였던 것 같지만, 나는 그 생각을 하는데에 꽤 오래걸렸다.
• 처음에는 queue에 (x, y, 부순적 있는지 true or false) 이렇게 담도록 하고,
  visited 배열은 map과 동일하게 2차원으로 만들어서 걸린 시간들만 누적하게 했는데,
  그렇게 하니까 예외가 생기더라,,! 그래서 다시 풀었다.
  
  => 백준 질문 검색에서 찾은 반례
  5 8
  01000000
  01010000
  01010000
  01010011
  00010010