BOJ 2178 DFS? BFS? DP?

문제

 

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1 복사

4 6 101111 101010 101011 111011

예제 출력 1 복사

15

예제 입력 2 복사

4 6 110110 110110 111111 111101

예제 출력 2 복사

9

예제 입력 3 복사

2 25 1011101110111011101110111 1110111011101110111011101

예제 출력 3 복사

38

예제 입력 4 복사

7 7 1011111 1110001 1000001 1000001 1000001 1000001 1111111

예제 출력 4 복사

13

---

해설

 

풀이는 다음과 같다. 

 

	// BOJ 2178 미로 탐색
	import java.io.*;
	import java.util.*;
	class Main {
	public static boolean arrived[][];
	public static int w, h;
	public static char[][] input;
	public static int D[][], point[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	public static ArrayDeque<Integer[]> deque = new ArrayDeque<>();
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String[] arr = br.readLine().split(" ");
	h = Integer.parseInt(arr[0]);
	w = Integer.parseInt(arr[1]);
	input = new char[h][w];
	arrived = new boolean[h][w];
	D = new int[h][w];
	for(int i = 0; i < h; i++){
	input[i] = br.readLine().toCharArray();
	}
	arrived[0][0] = true;
	D[0][0] = 1;
	solve(0, 0);
	while(!deque.isEmpty()) {
	Integer[] next = deque.pollFirst();
	solve(next[0], next[1]);
	}
	System.out.println(D[h - 1][w - 1]);
	}
	public static void solve(int y, int x){
	if(y == h - 1 && x == w - 1){
	return;
	}
	for(int[] el : point){
	int ty = y + el[0];
	int tx = x + el[1];
	if(0 <= ty && ty < h && 0 <= tx && tx < w) {
	if(input[ty][tx] == '1' && !arrived[ty][tx]) {
	Integer[] next = {ty, tx};
	arrived[ty][tx] = true; // 중요한
	D[ty][tx] = D[y][x] + 1;
	deque.addLast(next);
	}
	}
	}
	}
	}

view raw 미로 탐색.java hosted with ❤ by GitHub

DFS

이 문제를 처음 풀었을 땐, DFS를 이용해서 풀었다. DFS와 BFS의 차이에 대해 깊게 생각해 본 적도 없고, 둘 다 그래프의 탐색의 방법이니 상관이 없을 것이라 생각했다.  

 

계속 시간초과가 나는 걸 확인할 수 있었다. 

DFS로 할 경우, 어느 한 지점에서 탐색할 수 있는 곳이 전에 지난 곳을 제외한 3곳이기 때문에 O(3^(w * h))의 시간 복잡도를 가지기 때문에 위와 같이 시간 초과가 나게 된다.

 

DP

두 번째로 생각한 풀이는 어느 한 지점에서 도착 지점까지 가는 방법의 최소값을 기록하는 DP형태의 풀이였다.

도착 지점에서부터 시작해서 상하좌우를 탐색하면서 1씩 더하면 될 것 같은 느낌을 받았다. 하지만 막상 해보니 구현이 막막했다. 기존의 DP에선 최적 부분 구조를 파악하고, 작은 문제가 큰 문제를 해결할 수 있다는 걸 파악해야 하는데, 도저히 그러한 부분이 보이지 않았다.

나중에 생각하고 알게 된 것이지만, 이제까지 풀었던 DP 문제의 경우, 어느 한 지점에서 오른쪽 혹은 아래로 가는 방법만 있는 그러한 조건이 있는 문제였기 때문에, 한 번 지나친 것에 대해 다른 값을 가질 일이 없었지만, 이 미로 탐색 문제의 경우, 상하좌우 모두 가능하며, 이 마저도 0은 못 가기 때문에 이미 지나친 곳이 다른 값을 가질 수 있다는 게 문제였다. 즉 점화식 형태로 표현할 수 없는 문제이기 때문에 DP를 통해선 해결할 수 없는 문제였다.

 

BFS

그렇게 고민하다가, 알고리즘 분류를 확인했는데, 이 문제의 경우 BFS라고 적혀있었다. 

BFS로 할 경우, 시작 지점에서부터 깊이가 아닌 너비를 먼저 확인하고, 이후 도착 지점에 도착할 경우, 이 때의 깊이를 파악하면 되기 때문에 BFS로밖에 풀 수 없는 문제였다. 뿐만 아니라, 같은 깊이의 노드에 대해 탐색을 완료했다는 의미의 arrived [y][x] = true를 해주면, 어떤 칸 input [y][x]는 최소 깊이를 가질 때의 탐색만 처리하게 된다. 

46번째 라인을 28번째로 옮길 경우, 직접 탐색할 때 도착 표시를 하기 때문에, 최소 깊이를 가질 때의 탐색만 하는 것이 아닌, 이후의 더 큰 깊이를 가질 때의 탐색도 하게 된다. -> 궁금하면 바꿔보고 디버깅을 통해 따라가보자. 메모리 초과가 날 것이다.

 

즉, 이 문제의 경우 시작에서 도착까지의 깊이를 묻는 문제였고, 어떤 칸이 최소 깊이를 가질 때의 탐색을 묻는 것이기 때문에 BFS로 문제를 풀어야 한다. 

느낀 점

• BFS와 DFS를 문제를 풀 때, 고려하지 않았는데, 고려해야 함을 알게 해준 문제였다.