https://www.acmicpc.net/problem/2206
단순한 bfs를 이용한 길 찾기 문제에서 최대 1회 벽을 부술 수 있다는 조건이 추가된 문제이다.
과거에 풀었던 문제들 중, 벽 3개를 제거하고 난 뒤의 최단 거리를 구하는 문제가 생각났었다.
그때는 모든 벽들 중 3개 조합을 선택하여 제거한 상태에서의 bfs들 중 최솟값을 구했었다.
하지만 이 문제는 행렬의 크기가 최대 1000 x 1000이기 때문에 모든 벽들을 하나씩 제거해 보면서 모든 케이스에 대해 bfs를 시행하는 것은 시간이 초과가 날 수 있다고 생각했다.
따라서 시작점부터 한 번의 bfs를 하되, 현재 벽을 파괴한 상태인지 아닌지 구별하는 Boolean 변수를 탐색에 추가하여 구현해보기로 했다.
data class Pos(
val v: Int,
val h: Int,
val distance: Int,
val isBroken: Boolean
)이런 식으로 bfs에 사용될 data class를 정의하였다.
v는 vertical(세로 위치, y좌표)
h는 horizontal(가로 위치, x좌표)
distance는 현재까지의 이동 거리
isBroken은 벽을 1회 부쉈는지 여부이다.
이를 이러한 방식으로 사용한다.
bfs를 하는 도중 다음 위치가 벽(1)이고 현재 isBroken이 false라면 isBroken을 true로 만들고 벽 위치를 큐에 삽입한다.
다음 위치가 벽(1)이고 현재 isBroken이 true라면 더 이상 부술 수 없으므로 그 위치에서의 탐색을 멈춘다.
처음엔 이 정도 구상을 하고 그대로 구현했으나 실패했다.
배열을 통해 방문 체크를 하며 진행하는 bfs의 특성을 주의해야 한다
바로 위 행렬을 통해 예시를 들어보겠다.
왼쪽 경로가 정답에 해당하는 경로이고, 주의해야 하는 위치는 오른쪽 노란색 경로이다.
위 행렬에서, bfs를 통해 노란색 위치에 도달하는 방법은 두 가지가 존재한다.
(2, 0)에서 (2, 1)의 벽을 뚫고 도달하는 방법과, (3, 0)을 지나 도달하는 방법이 있다.
bfs를 아래 방향부터 진행하고 우측으로 진행한다면 문제가 없겠지만, 만약 (2, 0)에서 우측을 먼저 진행하고 아래로 진행하게 된다면??
위 그림처럼 (2, 1)에서 노란색 위치를 방문 체크하게 될 것이고, 다음으로 큐에서 꺼낸 (3, 0)에서는 노란색 위치로 확장하려다 방문체크가 되어있는 것을 보고 확장하지 않을 것이다.
하지만 (2, 1)의 벽을 부수고 노란색 위치에 도달하면 (3, 2)의 벽을 부수지 못하기 때문에 -1이 출력되게 된다.
이 점을 주의해야 한다.
내가 생각한 포인트는, 특정 위치에 도착한 노드들이 여러 개라면 무조건 isBroken이 false (벽을 부수지 않고 도달한 경로)인 노드가 무조건 중요하다는 것이다.
생각해보면 당연하다. bfs를 통해 같은 비용으로 같은 위치에 도달했으면 벽을 부수지 않고 도달한 케이스를 우선하고 나머지는 필요없는 것이다.
이를 위해 부수지 않고 도달 가능한지 여부를 표시하기 위한 체크 배열을 하나 더 사용하였다.
(2, 1)에서 (3, 1)을 확장할 때엔 isBroken이 true이고, 현재 상태에선 부수지 않고 도착할 수 있는지 모르므로 (3, 1)에 대해 배열에 false로 표시한다.
그 다음 (3, 0)에서 (3, 1)을 바라본다.
(3, 0)에서는 isBroken이 false이고, 배열에 (3, 1)위치가 false로 표기되어 있으므로 방문 체크와 관계 없이 (3, 1)을 확장한다.
이 때 (3, 1)에 isBroken이 false인 상태로 도달하였으므로 배열에 true로 표시한다
성능을 위해서 isBroken이 true인 노드가 배열에 true로 표기된 위치를 확장하려 하면 취소시키도록 하였다.
(이미 벽을 부순 적이 있는 노드가 부수지 않고 도착할 수 있는 위치에 도달하면 확장할 필요가 없다)
import java.util.*
val dir = listOf(-1, 0, 1, 0, -1)
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (N, M) = readLine().split(' ').map{it.toInt()}
var shortest = -1
val field = Array(N){readLine().toCharArray()}
fun bfs(){
val queue: Queue<Pos> = LinkedList()
val visited = Array(N){Array(M){false}}
val passWithoutBreak = Array(N){Array(M){false}}
queue.offer(Pos(0, 0,1, false))
visited[0][0] = true
passWithoutBreak[0][0] = true
while(queue.isNotEmpty()){
val next = queue.poll()
if(next.v == N - 1 && next.h == M - 1){
if(shortest == -1 || shortest > next.distance){
shortest = next.distance
return
}
}
for(i in 0..3){
val nextV = next.v + dir[i]
val nextH = next.h + dir[i + 1]
if(nextV in 0 until N && nextH in 0 until M){
if(next.isBroken && passWithoutBreak[nextV][nextH]) continue
if(field[nextV][nextH] == '0' && !passWithoutBreak[nextV][nextH] && !next.isBroken){
visited[nextV][nextH] = true
passWithoutBreak[nextV][nextH] = true
queue.offer(Pos(nextV, nextH, next.distance + 1, next.isBroken))
}else if(field[nextV][nextH] == '0' && !visited[nextV][nextH]){
visited[nextV][nextH] = true
queue.offer(Pos(nextV, nextH, next.distance + 1, next.isBroken))
}else if(field[nextV][nextH] == '1' && !next.isBroken){
queue.offer(Pos(nextV, nextH, next.distance + 1, true))
}
}
}
}
}
bfs()
print(shortest)
}부수지 않고 도달 가능한 지 여부를 passWithoutBreak에 표시하였다.
bfs 확장 부분에서
-
isBroken이 true이고(부순 적 있고), passWithoutBreak[다음 위치]가 true라면 (다음 위치가 부수지 않고 도달 가능하면) 확장하지 않는다.
-
다음 위치가 벽이 아니고(0이고) 부수지 않고 도달 가능한지 모르는 상태이며(false이며) 현재 isBroken이 false라면, visited를 통한 방문 체크보다 우선하여 확장한다.
-
그렇지 않으면 visited를 통해 방문 체크하며 일반 bfs를 시행한다.
-
다음 위치가 벽이고 isBroken이 false이면 isBroken을 true로 바꾼 후 다음 위치로 확장한다.
