[BOJ 14442 벽 부수고 이동하기 2]로 알아보는 조건이 있는 BFS
문제 읽기
벽이 존재하는 N*M 필드의 (1, 1)에서부터 (N, M)까지 도달할 수 있는 최단 경로의 길이를 구해내는 문제이다. 여기까지만 읽으면 단순한 BFS 문제이지만, 문제는 '벽을 부술 수 있다'는 점에 있다.
만일 벽을 부수고 지나갈 때 경로가 더 짧아진다면, 벽을 부술 수도 있다. 단, 최대 K회까지 가능하다. 그러니까, 단순히 벽에 가로막히고 말고만을 따지는 단순한 BFS로는 문제를 풀 수 없다는 것이다. 이런 문제는 어떻게 풀어야 할까?
BFS의 본질
우선, 우리가 최단경로를 구하기 위해 BFS를 수행하는 과정을 생각해보자. BFS를 수행하는 과정을 간단히 서술해보면 다음과 같다.
- 시작 지점을 큐에 넣고, 방문 표기를 한다.
- 이후, 큐가 빌 때까지 다음을 반복한다 :
- 큐에서 값을 하나 꺼낸 후, 그 값이 목적지인지 확인한다. 목적지라면, 경로를 찾은 것이므로 반복을 종료한다.
- 목적지가 아닌 경우, 현재 지점으로부터 나아갈 수 있는 모든 지점을 확인한다. 나아갈 수 있는 지점들 중, 아직 들르지 않은 지점이 있다면, 그 지점은 최단경로의 일부가 될 수 있는 후보가 된다! (이때 '특정 지점을 들렀느냐 들르지 않았느냐'는 방문 표기 여부로 판단한다.)
- 위의 기준으로 적합하다고 판단된 지점을 큐에 넣는다.
- 큐가 비었다면, 갈 수 있는 모든 지점을 가보았다는 의미이다. 만일 큐가 빌 때까지 목적지에 도달하지 못했다면, 목적지에 도착할 수 없다는 뜻이다.
위의 BFS를 수행하는 과정을 잘 살펴보면, '이미 방문했다고 표기된 지점을 다시 들른 순간, 최단거리가 되지 않는다'는 전제가 깔려있음을 알 수 있다.
사실, 그 이유는 아주 간단하다! 정말 단순한 예시로, A라는 지점부터 B라는 지점까지의 최단경로를 구해야한다고 해보겠다. 떠. A와 B 사이에는 많은 지점이 있겠지만, 그 중 C라는 지점이 있다고 해보자. C라는 지점을 30분만에 갈 수 있는 경우와, 1시간만에 갈 수 있는 경우. 둘 중 어느 것이 최단경로가 될 가능성이 있을까? 당연하게도, 30분만에 갈 수 있는 경우이다. 왜냐하면, 중간지점 C로부터 B까지의 걸리는 최소의 시간은 하나로 정해져 있다. C에서 B까지 가는데에 최소 1시간 30분이 걸린다고 가정해보면, 전자의 경우는 A부터 B까지 걸리는 시간이 총 2시간, 후자의 경우는 2시간 30분이다. 즉, 특정한 지점에 도착하는데에 더 오래 걸리는 경우의 수는, 최단거리가 될 가능성이 완전히 없기 때문에 배제하는 것이다.
BFS에서의 방문 표기의 의미
위처럼 최단이 될 수 없는 경우의 수를 배제하기 위해, BFS를 시행할 때에는 방문표기를 시행한다. BFS를 시행할 때에는 큐라는 자료구조를 사용하는데, 이 때문에 BFS의 대상이 되는 경우의 수는 무조건 시간 순으로 고려하게 된다.
1회 이동하여 갈 수 있는 지점들 → 2회 이동하여 갈 수 있는 지점들 → 3회 이동하여 갈 수 있는 지점들 → ... (이하 반복)
때문에, BFS 과정 중 먼저 고려하게 되는 경우의 수가 더 짧게 이동한 경우이다. 앞에서 도착할 수 있었던 지점을 뒤에서 또 도착한다고 하더라도, 뒤의 경우는 무조건 앞의 경우보다 더 먼 길을 통해 도착하거나, 아무리 빠르더라도 앞의 경우와 같은 길이의 경로를 거친다. 때문에 우리는 BFS를 이용해 최단거리를 구할 때, 한 번 도착해본 지점에 대해서는 고려하지 않아도 되는 것이다. 어차피 앞에서 더 빠르게 도착했으니, 다시 고려할 필요가 없다는 거다.
간단하게 다시 정리하자면 다음과 같다. BFS에서 방문 표기를 하는 이유는, 이전에 이미 도착해 본 지점을 또다시 도착해보았자, 그 경로는 최단경로가 되지 않기 때문이다.
빨리 도착한다고 다가 아니라면?
이번 문제처럼, 최단경로를 구할 때 또다른 조건이 추가되는 경우가 있다. 이렇게 되면, 단순히 먼저 도착하는 경우만이 최단의 가능성을 지니게 되는 게 아니게 될 수 있다.
아까처럼 간단한 예시를 들어보자. A부터 B까지 최단경로를 구하는 게 목적이고, C라는 중간지점이 있다. 이번에는 [벽 부수고 이동하기] 문제와 비슷하게, 길을 가다가 방해물이 있는 경우, 그걸 딱 한 번 부수고 지나갈 수 있다고 해 보겠다. 고려해볼 첫 번째 경우는, C에 30분만에 도착하는 경우이다. 다만, 이 경우는 C까지 빠르게 도착하기 위해, 오는 길에 이미 방해물을 부수고 왔다. 두 번째 경우는, C에 1시간만에 도착하는 경우이다. 이 경우는 길을 조금 돌아온 대신, 방해물을 부수지 않았다. 두 경우 중 어떤 경우가 최단의 가능성을 지니고 있을까?
정답은, 둘 다 가지고 있다. 왜냐하면, 두 경우는 장애물을 부순 횟수가 다르기 때문이다. 첫 번째 경우는, C까지 도착하는 과정 중에 방해물을 한 번 부쉈다. 즉, C부터 B까지 향할 동안은 방해물을 부술 수 없다는 뜻이다. 반대로, 두 번째 경우는, C까지 오는동안 방해물을 하나도 부수지 않았다. C부터 B까지 향할 동안, 방해물을 부술 수도 있다는 뜻이다.
C에서 B까지 걸리는 시간이, 방해물을 부쉈을 때에는 15분, 부수지 못할 때에는 1시간이라고 해보자. 그렇게 되면 첫 번째 경우의 A →B 소요시간은 총 1시간 30분, 두 번째 경우의 A →B 소요시간은 총 1시간 15분이다. C까지 도착하는데에 걸리는 시간이 더 길었음에도, 두 번째 경우가 최단의 경우가 된다는 거다!
이처럼, 경로를 지날 때 특수한 조건이 추가되면, 더 오래 걸려 도착하는 경우를 완전히 배제할 수 없는 일이 생기기도 한다. 나는 이런 문제를 개인적으로 조건이 있는 BFS, 혹은 특수 BFS라고 부르고 있다.
'조건이 있는' BFS
위의 장황한 내용을 통해 내가 설명하고자 했던 내용을 요약하면 다음과 같다. [벽 부수고 이동하기] 처럼, 단순히 더 빨리 도착한 경로만이 최단의 가능성을 지니게 되는 게 아닌 문제가 있다. 즉, 단순한 방문여부 표기만으로는 최단 경로를 구할 수 없다. 이런 문제를 풀 때에는, 어떤 요인이 최단이 될 가능성에 영향을 미치는가에 대해 고민해볼 필요가 있다.
이번 문제에서 최단의 가능성에 영향을 주는 요인은, 벽을 부순 횟수이다. 경로를 설계할 때, 최대 K회까지 벽을 부술 수 있다는 것이 이 문제의 조건이었다. 벽을 부수면 돌아가야 할 길을 생략할 수 있기 때문에, 벽을 부술 수 있는 횟수가 많을수록, 현재 탐색하고 있는 경로가 앞으로 더 짧은 경로를 찾을 가능성이 올라간다. 이런 점을 고려하여 BFS를 설계하려면 어떻게 해야할까? 말이 좀 거창한데, 단순하게 정리하자면 이런 질문이다 : 어떤 경우에, 더 늦게 도착해도 최단의 가능성이 있다고 쳐줄 것인가?
방문 표기 체계 구성
최단이 될 가능성에 영향을 미치는 요인은 다음 두 가지이다 : 도착할때까지 거친 경로의 길이, 앞으로 벽을 부술 수 있는 횟수. 전자를 위해서, 우리는 항상 각 지점에 대응되는 boolean값을 기록했었다. 하지만, 이번에는 더 늦게 도착했더라도, 앞으로 벽을 더 많이 부술 수 있다면 그 경우도 고려해줘야 한다. 그렇다면 방문 배열에 방문여부만 기록하지 말고, 방문했을 당시 지금까지 벽을 부순 횟수를 기록하는 건 어떨까?
A→B의 최단경로를 구해야하며, 그 중간에 C라는 지점이 있다는 예시를 다시 들어보자. 이번에는 장애물을 최대 K회 부술 수 있다고 해보자. 처음에 C라는 지점에, K+1이라는 숫자를 기록해둔다. 가장 첫번째로 C라는 지점에 도착한 경우는, 장애물을 전부 부수고 온 지라 장애물을 K회 부쉈다. 이 K라는 숫자를 C 지점에 기록해 둔 K+1과 비교해보면, 당연하게도 K가 더 작은 숫자이다. C라는 지점에 더 적게 벽을 부수고 도착했으니, 통과시킨다. 그리고, C 지점에 기록해둔 숫자를 K로 변경한다.
그 다음의 경우는, C라는 지점에 도착하는 동안 장애물을 K-3회 부쉈다. C 지점에 기록된 K와 비교해봤을 때, K-3이 더 작은 숫자이다. 이전의 경우보다 좀 더 돌아서 도착했지만, 앞으로 벽을 부술 수 있는 기회가 3번이 남은 것이다. 때문에 이 경우도 최단이 될 가능성이 있다. C 지점에 기록한 숫자를 K-3로 변경시킨 후, 통과시킨다.
또 다음의 경우는, 도착할동안 장애물을 K-1회나 부쉈다. C 지점에 기록된 K-3와 비교해보면... 이번 경우가 벽을 더 많이 부쉈다. 더 늦게 도착했는데, 앞으로 벽을 부술 수 있는 횟수가 적기까지? 이런 경우는 도착할 때까지 거친 경로의 길이도 더 길고, 앞으로 벽을 부술 기회도 모자라므로, 최단의 가능성이 없다. 때문에 이 경우는 더 고려하지 않고 폐기한다.
위의 과정을 이해할 수 있었을까? 최단의 가능성에 해당하는 경로의 길이, 그리고 벽을 부술 수 있는 횟수를 동시에 고려하며, 각각의 경우가 최단의 가능성이 있는지 아닌지를 고려하고 있다. 이 문제의 경우, 위의 방식대로 구성하면 2차원 int형 배열을 이용해 모든 가능성을 따질 수 있다.
코드
아래는 실제로 문제 풀이에 제출한 코드이며, Java 8로 작성되어있다.
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception{
/* 입출력 관련 객체 작성 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
/* [풀이 전략]
* 마찬가지로 특수 BFS인데, 이번에는 벽을 K회까지 부술 수 있다. 이때 K는 1보다 크거나 같고 10보다 작거나 같다.
* 규모가 조금 커졌을 뿐, 기존 문제와 마찬가지로 벽을 부순 횟수를 방문배열 대신에 사용하면 될듯하다.
* N과 M이 좀 커서 시간이 오래 걸릴듯함.
* */
// 첫번째 줄 : N, M, K
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
// 이후 N개의 줄동안 맵 정보가 주어진다
// 지나갈 수 있음 : true / 지나갈 수 없음 : false
boolean[][] map = new boolean[N][M];
for(int n = 0 ; n < N ; ++n) {
char[] input = br.readLine().trim().toCharArray();
for(int m = 0 ; m < M ; ++m) {
if(input[m] == '0') { // 지나갈 수 있는 공간이라면 true로 표기
map[n][m] = true;
}
}
}
// 입력받기 종료
// 방문배열은 벽을 부순 횟수를 기록하는 2차원 int 배열로 한다.
int[][] visited = new int[N][M];
for(int n = 0 ; n < N ; ++n) {
Arrays.fill(visited[n], 11); // 방문한 적 없음을 최대 부술 수 있는 벽의 횟수보다 높은 숫자로 표기
}
// BFS 준비
ArrayDeque<int[]> q = new ArrayDeque<>();
// 출발점은 (0, 0)
q.offer(new int[] {0, 0, 0}); // 인덱스 2 : 지금까지 벽을 부순 횟수
visited[0][0] = 0;
// 시작하는 칸을 포함하여 센다는 점에 주의
int count = 0;
// BFS 시작
boolean found = false;
while(!found && !q.isEmpty()) {
count++;
int size = q.size();
for(int s = 0 ; s < size ; ++s) {
int[] info = q.poll();
int x = info[0];
int y = info[1];
int broken = info[2];
// 도착지점에 도착했다면 루프를 탈출한다.
if(x == N-1 && y == M-1) {
found = true;
break;
}
// 도착하지 않았다면, 가능한 경우의 수를 탐색
for(int d = 0 ; d < 4 ; ++d) {
int nextX = x+dx[d];
int nextY = y+dy[d];
if(nextX < N && nextX >= 0 && nextY < M && nextY >= 0) {
// 유효한 인덱스 범위 내이면 이동을 시도할 수 있다.
// [1] 이동할 공간이 벽이 아닌 경우
// 현재의 broken과 지점에 기록된 broken을 비교한다.
if(map[nextX][nextY] && visited[nextX][nextY] > broken) {
visited[nextX][nextY] = broken;
q.offer(new int[] {nextX, nextY, broken});
}
// [2] 이동할 공간이 벽인 경우
// 벽을 부술 기회가 남아있다면, 진행을 시도
else if(!map[nextX][nextY] && broken < K) {
int nextBroken = broken+1;
if(visited[nextX][nextY] > nextBroken) {
visited[nextX][nextY] = nextBroken;
q.offer(new int[] {nextX, nextY, nextBroken});
}
}
}
}
}
}
// 반복 종료
// 결과를 출력한다.
if(!found) {
System.out.println(-1);
} else System.out.println(count);
}
}마치며
조건이 있는 BFS는 최단 가능성을 어떻게 따질 것인가에 대한 고민을 충분히 한다면, 일반 BFS와 크게 다르지 않게 풀 수 있는 문제이다. 이 문제의 경우 2차원 배열만을 이용해 모든 가능성을 따질 수 있었지만, 사실 대부분의 특수 BFS는 3차원 이상의 배열을 사용한다. 2차원 배열만으로 특수 BFS를 풀기 전에는, 정말로 최단의 가능성을 모두 고려했는지를 꼼꼼히 생각하도록 하자. 나도 다 생각 못 하고 2차원 배열로 밀다가 많이 틀렸다...
아는 사람들과 스터디를 진행하다가, 이 문제를 2차원 배열로 푸는 방식이 특이하다는 말을 들어서 한 번 정리해보았다. 누군가에게 이 글이 도움이 되었다면... 정말 영광이다! 앞으로의 문제 풀이에 참고해주면 고맙겠다.