백준 알고리즘 2206 - 벽 부수고 이동하기1

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

  백준 알고리즘의 2206번 문제 '벽 부수고 이동하기1'입니다.

 

  제가 여지껏 풀어왔던 행렬 길탐색 문제들은 전부 DFS와 가지치기로 풀리는 문제들이었습니다. 그런데 이 문제는 DFS와 가지치기로 코드를 작성해도 풀리지 않더라구요.

 

  결론적으로 이번 문제를 풀면서 BFS가 DFS보다 빠르다는 확증을 얻었습니다. 평소에는 머리로는 알고 있었지만 전부 DFS로 풀어도 해결이 되었기에 깊게 고민해본 적이 없었거든요. 그런데 DFS로는 안되지만 BFS로는 되는 문제를 눈 앞에 가져다주니 부정하려해도 부정할 수 없게 되었습니다.

 

 

DFS 코드

import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;

public class Main_BJ_2206_벽부수고이동하기_dfs {
		
	private static int N, M, min = Integer.MAX_VALUE;
	private static int[][] input;
							// 상   하   좌   우
	private static int[] dy = {0, 0, 1, -1};
	private static int[] dx = {-1, 1, 0, 0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		input = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			String[] parse = br.readLine().split("");
			for(int j = 0; j < M; j++) {
				input[i][j] = Integer.parseInt(parse[j]);
			}
		}
		
		// x, y, count, broken: 벽을 깬 횟수
		input[0][0] = 2;
		dfs(0, 0, 0, 0);
		
		if(min == Integer.MAX_VALUE) System.out.println("-1");
		else System.out.println(min+1);
	}
	
	private static void dfs(int x, int y, int count, int broken) {
		if(count >= min) return;
		// x, y가 N-1, M-1에 도달함.
		if(x == N-1 && y == M-1) {
			if(min > count) min = count;
			return;
		}
		
//		// broken이 1인데 벽을 만남.
//		if(input[x][y] == 1 && broken == 1) return;
		
		// 4방 탐색.
		for(int i = 0; i < 4; i++) {
			// 원래 input 값을 저장
			int ty = y + dy[i];
			int tx = x + dx[i];
			
			// 지나간 길은 2로 표시
			if(tx >= 0 && tx < N && ty >= 0 && ty < M) {
				int temp = input[tx][ty];
				if(input[tx][ty] == 0) {
					input[tx][ty] = 2;
//					show();
					dfs(tx, ty, count+1, broken);
				}else if(input[tx][ty] == 1 && broken == 0) {
					input[tx][ty] = 2;
//					show();
					dfs(tx, ty, count+1, broken+1);
				}
				
				input[tx][ty] = temp;
			}
		}
	}
	
	private static void show() {
		for(int i = 0; i < N; i++) {
			System.out.println(Arrays.toString(input[i]));
		}
		System.out.println("=====================");
	}
}

 

  그래서 지금껏 한번도 해보지 않은 BFS로 길을 탐색하는 과정을 해보기로 했습니다. 사실 이런 선택은 이미 BFS가 DFS보다 빠르다는 지식을 가지고 있었기 때문에 빠르게 선택할 수 있었던 것입니다. 보통은 DFS에서 가지치기하려고 몸부림치시다가 지치셔서 이렇게 제 블로그에 접속하게 되실 겁니다.

 

  BFS에서 체크해야할 점은 '벽을 부순다는 것을 어디까지 확인해줄 것인가' 입니다.

  DFS에서는 다음으로 넘기는 parameter를 통해 이를 제어하다가 한번 더 벽을 만났을 경우 멈추는 것이 가능하지만, BFS에서는 'visited'때문에 꼬이게 됩니다. DFS의 경우에는 탐색 진행 중에 길을 표시해주다가 '아니다!'라는 결론을 얻었으면 다시 돌아가면서 표시를 원상태로 복구하는 것으로 이미 지났던 길을 중복 체크하는 것을 방지해줍니다. 하지만 BFS에서 이는 불가능한 일입니다. 따라서 보통 visited 배열을 통해 이를 제어해주게 되는데, 문제는 다음과 같은 상황에 발생합니다.

 

 

5 5
00000
11101
000'0'1
01111
00010

 

 

  왜 문제인지 보이시나요?

  이 예시의 문제점은 제가 강조해놓은 (3, 4)를 지날 때 이미 벽을 부수고 온 경우의 탐색이 벽을 부수지 않고 온 경우의 탐색보다 빠르게 오기 때문에, 해당 칸의 visited을 이미 true로 변경하고 지나가 벽을 부수고 오지 않아 더 진행할 수 있음에도 후자의 탐색이 여기까지 미치지 않는 것입니다.

 

  따라서 이를 해결하고자 3차원 배열을 만들어 벽을 부순 경우와 부수지 않은 경우의 visited을 따로 관리하는 방식으로 문제를 푸는 분들도 계십니다. 하지만 저는 왜인지 모르는 오기(?)가 생겨 꼭 2차원 배열을 쓰고 싶었습니다. 그래서 visited 배열을 boolean 타입이 아닌 int 타입으로 변경하여 사용하였습니다.

 

  제 코드의 요지는 이것입니다. 결국 문제가 생기는건 벽을 부술 기회를 가진 탐색이 벽을 부술 기회가 없는 탐색보다 늦게 왔을 때 탐색하지 않은 것이므로 만일 어떤 칸에 대해 벽을 부술 기회가 없는 탐색이 지나가 체크한 visited의 경우는 전자가 볼 수 있도록 하면 되는 것입니다.

  따라서 저는 처음 해당 칸에 도달하였을 때에 '벽을 부쉈던 탐색'이 visited 체크할 때에는 2를 넣어주고, '벽을 부수지 않았던 탐색'이 visited 체크할 때에는 1을 넣어주었습니다. 그래서 이후 '벽을 부수지 않았던 탐색'이 visited이 2인 칸을 방문했을 때는 무시하고 탐색하도록 만들었습니다.

 

  아래가 그 코드입니다.

 

BFS 코드

import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;

public class Main_BJ_2206_벽부수고이동하기_bfs {
		
	/*
	 * 벽을 뚫고 안뚫고를 구별하지 않고 visited을 그냥 방문했는지에 대해서만 체크했을 때의 반례.
5 5
00000
11101
00001
01111
00010
	 */
	
	private static int N, M, min = Integer.MAX_VALUE;
	private static int[][] input;
							// 상   하   좌   우
	private static int[] dy = {0, 0, 1, -1};
	private static int[] dx = {-1, 1, 0, 0};
	private static int[][] visited;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		input = new int[N][M];
		visited = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			String[] parse = br.readLine().split("");
			for(int j = 0; j < M; j++) {
				input[i][j] = Integer.parseInt(parse[j]);
			}
		}
		
        // 시작점인 (0, 0)을 입력.
		bfs(0, 0);
		
		if(min == Integer.MAX_VALUE) System.out.println("-1");
		else System.out.println(min);
	}
	
	private static void bfs(int x, int y) {
		Queue<int[]> que = new ArrayDeque<int[]>();
		
		// x, y, broken
        // broken은 해당 element가 벽을 깬적이 있는지 여부를 체크해줍니다.
		que.offer(new int[] {x, y, 0});
		visited[x][y] = 1;
		int count = 1;
		
		while(!que.isEmpty()) {
			int size = que.size();
			for(int j = 0; j < size; j++) {
				int[] cur = que.poll();
				int cx = cur[0];
				int cy = cur[1];
				int broken = cur[2];
				
				// 가장 먼저 도착점에 도달했기 때문에 해당 단계의 count가 최소 거리입니다.
				if(cx == N-1 && cy == M-1) {
					min = count;
					return;
				}
				
				for(int i = 0; i < 4; i++) {
					int ty = cy + dy[i];
					int tx = cx + dx[i];
					
					if(tx >= 0 && tx < N && ty >= 0 && ty < M) {
						// 우선 0에 들어오면 visit 체크를 해준 후 que에 넣습니다.
						if(input[tx][ty] == 0 && visited[tx][ty] == 0) {
							// 이때, 벽을 깬 경험이 있는 경우에는 visited에 2를, 없는 경우는 1을 넣어줌으로써
							// broken이 0인 element가 해당 지점을 방문했을 때, broken이 1인 element가 훑고 지나가 visited가 켜진 것이라면 한번 더 보도록 만듭니다.
							if(broken == 1) visited[tx][ty] = 2;
							else visited[tx][ty] = 1;
							que.offer(new int[] {tx, ty, broken});
//							show(tx, ty, broken, count);
						}
						// visited이 2인 부분을 broken이 0인 element가 한번 더 확인하는 부분입니다.
						else if(input[tx][ty] == 0 && visited[tx][ty] == 2 && broken == 0) {
							visited[tx][ty] = 1;
							que.offer(new int[] {tx, ty, broken});
//							show(tx, ty, 1, count);
						}
						// 벽이 있을 경우 element의 broken이 0 즉, 벽을 깬 경험이 없는 경우에만 깨고 다음으로 넘어가도록 만듭니다.
						// 이때, broken은 1로 변경해줍니다.
						else if(input[tx][ty] == 1 && visited[tx][ty] == 0) {
							if(broken == 0) {
								visited[tx][ty] = 2;
								que.offer(new int[] {tx, ty, 1});
//								show(tx, ty, 1, count);
							}
						}
						
						
					}
				}				
			}
			// 해당 단계에서 bfs 탐색이 끝나지 않았으므로 count를 1 늘려줍니다.
			count++;
		}
	}
	
	private static void show(int x, int y, int broken, int count) {
		int[][] clone = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			clone[i] = input[i].clone();			
		}
		
		clone[x][y] = 9;
		
		for(int i = 0; i < N; i++) {
			System.out.println(Arrays.toString(clone[i]));
		}
		
		System.out.println("==========broken========= : " + broken);
		System.out.println("-----------------------");
		System.out.println(count);
		System.out.println("-----------------------");
	}
}

 

  어떻게 동작하는지가 궁금하시다면 코드를 가져가신 뒤에 군데군데 있는 show()의 주석을 풀어주면 탐색 과정을 눈으로 확인할 수 있습니다!

 

 

  오늘은 BFS로 길을 탐색하는 문제에 대해 풀어보았습니다. 이런 문제가 코딩테스트에 나와 우리를 괴롭힌다면 참 난해할 것 같다는 생각이 드는 하루입니다.

 

  다들 좋은 하루 되세요!