[Swift] 백준_벽 부수고 이동하기(2206)

문제

 

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

2206번: 벽 부수고 이동하기

 

 

풀이

 

처음 풀어보는 유형이라 너무 어려웠다..기본적인 틀 자체는 BFS문제들과 비슷하지만 벽을 부순다는 조건이 추가되었다.

 

처음에는 queue에 들어가는 배열에 벽을 부신 수를 추가해서, 만약 부신 벽이 1이면 더 이상 1쪽으로 갈 수 없게 구현하였다. 여기까진 괜찮은데 최단거리값을 가지는 배열 result가 2차원인 것이 문제였다. BFS의 코드에서 result값이 -1일때만 진행되는 형태이므로 이미 벽을 한 번 뚫고서 최단거리를 갖게된다면 더 이상 벽을 부술 수 없게 된다. 

이 경우에 마지막 바로 앞에 벽이 한 번 더 있다면 이미 벽을 뚫은 기록이 있기 때문에 돌아가는 길이 있어도 -1을 출력하게 된다. 

 

이 문제를 해결하기 위해서는 2차원 배열 두 개를 사용하거나 3차원 배열을 사용해서 현재까지 부신 벽의 수를 갖고 있어야한다. 그래야 최단거리 자체에만 영향받지 않고 벽을 부신 것까지 확인할 수 있다.

이 내용을 이해하는 것이 쉽지 않았다.

 

간단히 정리하면, [벽을 부수지 않은 경우, 벽을 하나 부순 경우] 두 경우를 같이 확인하는 것이다.

BFS이기때문에 주변을 하나씩 전부 탐색해서 큐에 넣어주는 것은 동일하다. 다만 1을 만났을 때, 바로 넘어가는 것이 아니라 이전까지 벽을 부순 적이 없는 경우에 대해서는 진행을 시켜줘야한다.

여기서 처음에 이해가 안됐던건, 위에 적었던 것처럼 이미 벽을 부신 기록이 있는 경우엔 어떻게 확인할까 생각이 들었다. 근데 벽을 부시지 않은 경우가 계속해서 진행되고 있기때문에 걱정할 필요가 없는 것이었다. 

예를 들어 어떤 칸의 result값이 [3,3]인 경우를 생각해보자. 벽을 부시지 않았을 때와, 벽을 부셨을 때 모두 최단거리가 3인 상태라는 의미이다. 이때, 큐에서 나온 값(current)의 마지막 값(벽을 부신 수)가 1인 경우에는 더 이상 진행할 수 없게 된다. 하지만 큐에는 current의 마지막 값이 0인 경우도 있을 것이다(최단경로를 찾을 수 있는 경우를 생각한 것임)

따라서, 바로 종료가 되지 않고 마지막 값이 1인 배열이 큐에 다시 추가되기때문에 계속해서 진행할 수 있다. 이 경우엔 status를 1로 바꿔주는 것을 잊으면 안된다.

 

정리를 못해서 다른 사람이 읽는다면 이해를 못할 수도 있겠지만, 위와 같이 구현하게 되면 또 참고해야 하는 사항이 있다. 현재 while문을 보면 이전의 다른 BFS문제처럼 queue가 빌 때까지 반복해주고있따(물론, 지금은 idx를 이용해서 다르긴 하지만 의미는 같다) 

위와 같이 구현하게 되면 (N,M)에 도착하더라도 큐에 원소가 남아있을 수도 있다. 그래서 따로 종료 조건을 추가해서 종료해줘야 한다.

만약, while문이 끝난다는 것은 불가능하다는 의미이므로 마지막에 -1을 출력하는 코드까지 작성해주었다.

import Foundation

var input = readLine()!.split(separator: " ").map { Int(String($0))! }
var board: [[String.Element]] = []
var result = Array(repeating: Array(repeating: Array(repeating: -1, count: 2), count: input[1]), count: input[0])
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
for _ in 0..<input[0] {
    board.append(readLine()!.map { $0 })
}
var queue: [[Int]] = []
var idx = 0
result[0][0][0] = 0
result[0][0][1] = 0
queue.append([0,0,0]) //좌표, 벽을 부셨는지
while idx < queue.count {
    let current = queue[idx]
    idx += 1
    if current[0] == input[0] - 1 && current[1] == input[1] - 1 {
        print(result[current[0]][current[1]][current[2]] + 1)
        exit(0)
    }
    for i in 0..<dx.count {
        let newX = current[0] + dx[i]
        let newY = current[1] + dy[i]
        let status = current[2] // 벽 부셨는지 안부셨는지
        if newX < 0 || newY < 0 || newX >= input[0] || newY >= input[1] {
            continue
        }
        if result[newX][newY][status] == -1 {
            if board[newX][newY] == "0" {
                //그냥 가면됨
                result[newX][newY][status] = result[current[0]][current[1]][status] + 1
                queue.append([newX,newY,status])
            } else {
                if status == 0 {
                    result[newX][newY][1] = result[current[0]][current[1]][status] + 1
                    queue.append([newX,newY,1])
                }
            }
        }
    }
}
print(-1)

 

 

_____________________________________________________________________________________________________

 

 

너무 오래걸려서 힘들었지만 조건이 추가되면 2차원 배열이 아닌 다차원배열을 이용해서 해결할 수도 있다는 것을 알게되었다.