[JAVA] 백준 2206번 : 벽 부수고 이동하기

 

---

 

• 생각

1. dfs로 푸는 방법 - 정확하게 풀 수 있다. 벽을 부수고 지나왔으면 그 다음 벽은 못 부수게 하면되고 안부수고 지나왔으면 다음 벽을 만났을 때 부술 수 있게 돌리면 된다. 최종으로 도달했을 때 가장 짧은 길이를 출력 ==>> 시간 초과

 

위의 사진은 어떤 분이 정리 해 둔 것인데 보면서 깨달으면 좋을 것 같아서 가져왔다.

 

1. 가중치가 없는 최단 경로는 무조건 BFS입니다. 왜 DFS가 안 될까요? 그 이유는 당연하게도, 특정 칸에 처음 도달했을 때까지의 경로의 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장이 전혀 없기 때문입니다. 아직까지 이 사실을 모르고 계셨다면, 이 문제는 아직 풀기에 너무 어렵습니다. 더 기본적인 BFS 문제을 먼저 풀어보세요.
2. 모든 칸을 전부 0으로 하나씩 바꾸어보고 BFS를 돌리는 것을 반복해서는 통과될 수 없습니다. 대부분의 알고리즘 문제가 그렇듯이, 풀이를 짜기 전에 반드시 해야 하는 것 중 하나는 시간 복잡도를 생각하는 것입니다. 시간 복잡도 계산, 전혀 어렵지 않습니다. 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색해야 하죠? 그러니 O((NM)^2)입니다. 이 수는 우리가 대충 1초에 돌 수 있다고 보는 단위인 1억을 10000배나 뛰어넘는 1조입니다. 절대 통과될 수 없겠죠?
3. 칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없습니다. 어떤 칸에 도달했을 때 나는 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있습니다. 큐에 그 상태를 넣은 것만으로 되는 것이 아닙니다. 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적으로 만들 수 있는 건 아닙니다. 구체적인 예시가 필요한가요?
   1. 현재 칸까지 벽을 안 부수고 최단으로 올 수 있었다고 가정해봅시다. 현재 지점에서 목표 지점까지 가는 데에, 벽을 한 개 부수고 가는 것이 안 부수고 가는 것보다 최적이 나온다고 해봅시다. 그렇다면 지금 내가 벽을 더 부술 수 있는 상태라는 사실을 알고 있어야만 되겠죠?
   2. 벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에서 목표 지점까지 가려면 무조건 벽을 한 개 부숴야만 된다고 해봅시다. 비록 현재 칸까지는 벽을 부수고 오는 것이 최적이었지만, 이 상태로는 끝에 아예 도달을 못 하죠? 현재 칸까지는 더 멀더라도 벽을 안 부수고 와야, 끝에 도달이 가능하죠.
4. (스포일러) 그래서 이 문제에서는 BFS에 대해 새로운 테크닉을 요구합니다. 단순히 좌표만을 큐에 넣어 탐색하는 방식을 넘어, "현재 상태" 자체를 큐에 넣어서 문제를 풀어야 합니다. 즉, 어떤 좌표에 있는가 뿐만 아니라, "여기까지 오면서 벽을 부순 적이 있는가" 여부를 함께 큐에 저장해서 탐색하고, 각각을 별개로 방문 체크해줘야 하는 문제입니다. visited[x][y]가 아니라, visited[x][y][벽을 부순 적이 있는가?] 가 되어야 합니다.
5. 이 문제에서는 같은 칸에 방문하는 경우 벽을 안 부순 것이 더 유리하기 때문에 벽을 부쉈는지 여부를 방문 배열에 기록하여 부순 횟수가 더 적을 때만 방문하는 방법도 됩니다. 그러나 이는 문제의 특성 때문에 이 문제에서만 통하는 그리디이므로 다른 문제에도 함부로 사용해서는 안 됩니다.

2. bfs로 푸는 방법 - 조건을 잘 설정하면 dfs보다 메모리는 더 쓰겠지만 속도는 빠를 것 같다. (시간과 메모리 제한 보고 알고리즘을 생각하는 정도의 수준까지 오면 좋을 것 같다. ==>> 공부를 열심히 해야할 듯.)

 

 

• 코드

정답 코드 : bfs로 풀었다. 여기서 핵심은 중복제거를 check[N][M][2]로 벽을 지나오면서 왔는지 아닌지 중복체크를 해주는 방법을 사용해야지만 정확히 풀 수 있는 문제이다. 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, minValue;
	static int[][] array;
	static boolean[][][] check;
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		SetData();
		bfs();
        if(minValue == Integer.MAX_VALUE)
            System.out.println(-1);
        else    
            System.out.println(minValue);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		array = new int[N][M];
		check = new boolean[N][M][2];
		minValue = Integer.MAX_VALUE;
		String s;
		
		for (int i = 0; i < N; i++) {
			s = br.readLine();
			for (int j = 0; j < M; j++) {
				array[i][j] = s.charAt(j) - '0';
			}
		}
	}

	private static void bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { 0, 0, 1, 0 });

		while (!queue.isEmpty()) {
			int location[] = queue.poll();
			
			int count = location[2];
			int breakWall = location[3];
			if (location[0] == N - 1 && location[1] == M - 1) {
				minValue = Math.min(minValue, count);		// 마지막 위치에 도달했을 때 지나온 칸 수를 return
			}

			for (int direction = 0; direction < 4; direction++) {
				int r = location[0] + x[direction];
				int c = location[1] + y[direction];

				if (r < 0 || r >= N || c < 0 || c >= M)
					continue;
				if (array[r][c] == 1 && breakWall == 1)	// 지나온 벽이 있고 다음 칸도 벽이면 진행 X
					continue;

				if (breakWall == 1) {
					if (!check[r][c][breakWall] && array[r][c] == 0) {
						check[r][c][breakWall] = true;
						queue.offer(new int[] { r, c, count + 1, breakWall});
					}
				} else { // 벽을 안부순 상태
					if (!check[r][c][breakWall] && array[r][c] == 1) {
						check[r][c][breakWall] = true;
						queue.offer(new int[] { r, c, count + 1, breakWall + 1 });
					} else if (!check[r][c][breakWall] && array[r][c] == 0) {
						check[r][c][breakWall] = true;
						queue.offer(new int[] { r, c, count + 1, breakWall });
					}
				}
			}
		}
	}
}