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

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

문제 설명

N x M 그리드로 표현되는 맵이 있고 각 칸이 이동 가능하면 0, 벽이 있어 이동이 불가능하면 1 로 이루어져 있다. (1, 1)에서 (N, M)의 위치까지 이동하는 최단 거리를 구하는 문제이다.

상하좌우로 이동가능하며 거리는 지나는 칸의 수이다.

만약 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

문제 풀이

그래프 상에서 최단 거리를 구하는 문제이면서, 가능한 이동의 선택들이 동일한 가중치(1칸 := 거리 1)를 가지므로 BFS로 풀이할 수 있다.

다만, 모든 경로에서 각각 한 번씩만 벽을 부수는 것이 가능하다는 조건이 붙는데,

https://velog.io/@rhqjatn2398/PS-백준-1600번-말이-되고픈-원숭이

이전에 풀이했던 백준 1600번 말이 되고픈 원숭이 문제와 매우 유사하다는 것을 알 수 있다.
그래서 백준 1600번 문제와 마찬가지로 N x M 2차원 그래프를 3차원으로 확장해야 한다.

그 이유는

1. 벽을 한 번 부순 상태에서 (i, j)정점을 방문한 것과
2. 벽을 한 번도 부수지 않은 상태에서 (i,j)정점을 방문한 것은
   문제정의상 다른 상태이기 때문이다.

여담

https://velog.io/@rhqjatn2398/PS-백준-1600번-말이-되고픈-원숭이
이전에 풀이했던 위 문제와 이 문제는 굉장히 유사한데, 위 문제에서는 3차원 정수 배열에 거리를 저장했다. 그 이유는 위 글을 참고. 이 문제 풀이에서는 3차원 boolean 배열에 방문 여부를 저장했다. 둘 다 구현해본 결과 BFS라는 개념과는 3차원 boolean 배열이 맞기는 한데 코드의 depth가 하나 늘어난다는 점이 단점이다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static Scanner sc = new Scanner(System.in);
	static StringTokenizer st;

	static int n, m;
	static int[][] grid;
	static boolean[][][] visited;
	static final int[] dy = { 0, 1, 0, -1 };
	static final int[] dx = { 1, 0, -1, 0 };

	static class MyPoint extends Point {
		int breakCnt;

		public MyPoint(int x, int y, int breakCnt) {
			super(x, y);
			this.breakCnt = breakCnt;
		}

	}

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		grid = new int[n][m];
		visited = new boolean[n][m][2]; // 0 := 벽을 안 부순 경우 1 := 벽을 부순 경우

		for (int i = 0; i < n; i++) {
			String line = br.readLine();
			for (int j = 0; j < m; j++) {
				grid[i][j] = line.charAt(j) - '0';
			}
		}

		System.out.println(go());
	}

	static int go() {
		Queue<MyPoint> queue = new ArrayDeque<>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				Arrays.fill(visited[i][j], false);
			}
		}
		visited[0][0][0] = true;
		visited[0][0][1] = true;
		queue.add(new MyPoint(0, 0, 0));
		
		int len = 1;
		while (!queue.isEmpty()) {
			int size = queue.size();
			
			for (int k = 0; k < size; k++) {
				MyPoint cur = queue.poll();
				
				if (cur.y == n - 1 && cur.x == m - 1) {
					return len;
				}
				
				for (int i = 0; i < 4; i++) {
					int nRow = cur.y + dy[i];
					int nCol = cur.x + dx[i];
					
					if (!inRange(nRow, nCol)) {
						continue;
					}
					
					// 이동할 칸이 벽이고 부술 수 있는 경우
					if (grid[nRow][nCol] == 1 && cur.breakCnt == 0 && !visited[nRow][nCol][cur.breakCnt + 1]) {
						visited[nRow][nCol][cur.breakCnt + 1] = true;
						queue.add(new MyPoint(nCol, nRow, cur.breakCnt + 1));
						
						continue;
					}
					
					// 이동할 칸이 벽이 아닌 경우
					if (grid[nRow][nCol] == 0 && !visited[nRow][nCol][cur.breakCnt]) {
						visited[nRow][nCol][cur.breakCnt] = true;
						queue.add(new MyPoint(nCol, nRow, cur.breakCnt));
					}
				}
				
			}
			
			len++;
		}
		
		return -1;
	}
	
	static boolean inRange(int row, int col) {
		return 0 <= row && row < n && 0 <= col && col < m;
	}
}