[2206] 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

// 2206 벽 부수고 이동하기
public class Main {
	static int N, M, cnt;
	static int[][] map;
	static boolean visited[][][];
	static Queue<Pair> queue;
	static int[][] temp = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static boolean flag;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		visited = new boolean[N][M][2];

		for (int i = 0; i < N; i++) {
			String st = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = st.charAt(j) - 48;
			}
		}
		visited[0][0][1] = true;
		BFS(0, 0, 1);

		if(flag == true) System.out.println(cnt);
		else System.out.println("-1");
		
	}

	public static void BFS(int x, int y, int drill) {
		queue = new LinkedList<Pair>();
		queue.offer(new Pair(x, y, drill));
		visited[x][y][drill] = true;

		Outter : while (!queue.isEmpty()) {
			int size = queue.size();
			
			for (int j = 0; j < size; j++) {
				Pair current = queue.poll();
				
				if(current.x == N-1 && current.y == M-1) {
					cnt++;
					flag = true;
					break Outter;
				}
				
				for (int i = 0; i < 4; i++) {
					int nextX = current.x + temp[i][0];
					int nextY = current.y + temp[i][1];

					if (!isInside(nextX, nextY))
						continue;

					// 벽면을 만나면
					if (map[nextX][nextY] == 1) {
						// 드릴을 가지고 있고, 드릴을 사용하지 않고 방문하지 않은것이 확인되었으면
						if (current.drill == 1 && visited[nextX][nextY][0] == false) {
							visited[nextX][nextY][0] = true;
							queue.add(new Pair(nextX, nextY, 0));
						}
					} else {
						// 이동할 수 있는 곳을 만나면
						if (visited[nextX][nextY][current.drill] == false) {
							visited[nextX][nextY][current.drill] = true;
							queue.add(new Pair(nextX, nextY, current.drill));
						}
					}
				}
			}
			cnt++;
		}
	}

	public static boolean isInside(int x, int y) {
		if (x >= 0 && x < N && y >= 0 && y < M)
			return true;
		else
			return false;
	}
}

class Pair {
	int x;
	int y;
	int drill;

	Pair(int x, int y, int drill) {
		this.x = x;
		this.y = y;
		this.drill = drill;
	}
}

---

최단거리를 구하는 문제이기 때문에 BFS로 구할 수 있다. BFS로 최단경로를 구하는 것은 간단하지만, 이 문제에서는 한가지 조건이 추가 된다. 이동하는 도중에 만나는 한개의 벽을 부술 수 있다는 것인데, 내가 처음에 생각 했던 생각은 입력을 받고 모든 1을 한번씩 빼면서 BFS를 하는 것 이었다. 하지만 그렇게 하면 되면 너무 비효율적이고 N, M의 입력이 1000까지 이었기 때문에 당연히 시간초과가 나왔다.

문제해결의 핵심 첫 번째는 방문하는 visited 배열을 3차원으로 선언하여 벽을 뚫고 온 길인지, 아닌지를 판단하는 것이다. 두 번째는 Pair 클래스의 x, y좌표 말고도 drill 변수를 추가로 두는 것이다. drill이 1이면 벽을 뚫 수 있는 drill 을 한개 가지고 있다는 뜻이고, 0이면 드릴을 썻기 때문에 더 이상 벽을 뚫 수 없다는 뜻이다.

그리고 또 하나 중요한 점은 최단거리를 어떻게 구하냐는지 이다. 구글링을 하다보니까 여기에서 BFS하면서 최단거리를 구하는 새로운 스킬? 같은 것을 처음 배울 수 있었는데, queue에 탐색할 좌표를 넣고 pop을 할 때 queue의 size만큼 for문을 반복하는 것이다. queue의 size만큼 for문을 반복하고 나온 후에 cnt 변수를 1씩 증가시키면 queue 안에 있던 탐색 가능한 좌표들이 한번 움직일 때 마다 거리를 몇만큼 움직이는지 체크하여 N-1, M-1 좌표에 도달 했을 때 최단 거리를 cnt변수로 출력할 수 있다. 이 부분은 queue의 size만큼 반복하는 for문을 보면 쉽게 이해 할 것이다. 처음 알게된 스킬?인만큼 잘 숙지해야겠다. 

< 문제 풀이 >

1. 처음 좌표인 0, 0에서 BFS를 시작하는데 드릴을 가지고 있으므로 BFS(0, 0, 1)을 처음 시작한다.

2. 그러면 queue에 (0,0,1) 이 들어가고, 주어진 첫번 째 예제를 예로들어 설명해보면 0,0 에서 갈 수 있는 방향은 0,1 과 1,0 이다. 하지만 둘다 벽이므로 갈 수 있는 모든 방향을 벽을 뚫어야 한다. 그러므로 0,0,1 을 pop하면서 좌표 1,0과 0,1 을 queue에 push 하는데 queue에 들어갈 좌표는 결론적으로 두가지를 확인해야 한다. 

① 벽면을 만났는데, 현재까지 드릴을 사용하지 않고 왔고, visited[nextX][nextY][0] == false 인지 확인해야 한다. visited[nextX][nextY][0] 이 뜻하는 것은 "벽면을 뚫지 않고 왔던 길이냐" 하는 것이다. 벽면을 뚫지 않고 온 길이여야지 벽면을 뚫 수 있기 때문이다. 만약에 ①번 조건을 만족시키면 드릴을 썻기 때문에 queue에 좌표와 드릴을 썻다는 의미로 0을 push하고 visited[nextX][nextY][0] 을 true 로 만든다. 이제 방금들어간 Pair는 드릴을 썻기 때문에 앞으로 좌표를 탐색할 때 벽면을 만나면 지나가지 못할 것이다. 

② 다음으로 이동할 수 있는 곳을 만나면 드릴이 있던 없던 지나갈 수 있으므로 visited 배열의 방문 표시만 해주고 지나가면 된다.

이렇게 queue 에 어떤 좌표를 넣을지를 판단하고

3. 마지막에 for 문을 빠져나오면 cnt 을 1 증가시켜 0,0 좌표에서 현재 위치까지 좌표를 업데이트 해준다.

4. queue에서 pop 한 좌표가 N-1, M-1 이면 BFS를 멈춘다. 여기에서 cnt를 왜 1증가시키냐면 처음 좌표를 0으로 잡아서 마지막에 1을 증가시켜야 답이 나오기 때문이다. 그리고 boolean 타입의 flag가 뜻하는 것은 목표 지점에 도달했느냐 안했느냐 이다. 목표 좌표인 N-1, M-1에 도달 했으면 true로 바꿔서 cnt를 출력해주고, 도착하지 못했으면 false 상태이므로 벽면에 막혀서 도달했지 못했다 라는 뜻이기 때문에 -1을 출력한다.