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

문제

 

 

접근 방식

여태까지 풀어본 BFS 문제 중 가장 어려웠던 문제인 거 같다...

 

일단 문제에서 중요한 포인트는 출발지에서 도착지까지 가는 동안

벽은 한 개까지만 부술 수 있다는 것이다.

 

길을 이동할 때마다 벽을 부순 적이 있는지 여부를 어딘가에 기록해야 됐고

이를 사용해 벽을 부순 적이 없다면 벽을 부수고 갈 수 있고

벽을 부순 적이 있다면 벽을 만났을 때는 더 이상 못 가게 해야 했다.

 

그래서 기존에 좌표를 기록하던 클래스에 추가로

벽을 부순 적이 있는지 여부를 저장하는 변수를 추가했다.

 

이 정도까지만 구현하고 코드를 돌려봤을 때 테스트 케이스는 성공했지만

실제 제출 한 결과는 실패로 떴다.

 

방문 여부 기록을 벽을 부수지 않은 상태와 부순 상태가 공유하기 때문에

발생한 문제였는데 문제점을 인지하고 해결하는 것에 생각보다 애를 먹었다.

 

우선 부순 상태의 방문 여부와 부수지 않은 방문 여부를 기록할 배열을 만들고

각각의 처리를 따로 해주었다.

 

부순 상태의 방문에는 부순 상태에 방문 여부만 기록하고

부수지 않은 방문 여부는 기본 방문 여부를 기록한 후에

추가로 방문한 위치가 벽이라면 부순 상태의 방문 여부에도 기록했다.

 

이동 중에 다음 칸을 방문할 수 없는 경우는 아래와 같다.

• 이미 방문한 적이 있는 경우
• 부순 상태로 왔을 때 이미 부순 상태로 방문한 적이 있는 경우
• 부순 상태로 왔을 때 벽인 경우

위 조건들에 해당하지 않는 경우만 방문할 수 있다.

 

이제 계속 탐색을 하면서 이동한 지점이 도착지점인지 확인해 주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int[] dx = {1, -1, 0, 0};
		int[] dy = {0, 0, -1, 1};

		String[] nm = br.readLine().split(" ");
		int n = Integer.parseInt(nm[0]);
		int m = Integer.parseInt(nm[1]);


		int[][] arr = new int[n][m];
		boolean[][] isVisited = new boolean[n][m];
		boolean[][] isBrokenVisited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			char[] input = br.readLine().toCharArray();
			for (int j = 0; j < m; j++) {
				arr[i][j] = input[j] - '0';
			}
		}

		if (n == 1 && m == 1) {
			System.out.println(1);
			return;
		}

		Queue<XY> queue = new LinkedList<>();

		queue.offer(new XY(0, 0, 1, false));
		isVisited[0][0] = true;
		isBrokenVisited[0][0] = true;

		while (!queue.isEmpty()) {
			XY cur = queue.poll();

			for (int dir = 0; dir < 4; dir++) {
				int x = dx[dir] + cur.x;
				int y = dy[dir] + cur.y;

				if (x < 0 || x >= n || y < 0 || y >= m) continue;
				if (isVisited[x][y] || (cur.isBroken && (arr[x][y] == 1 || isBrokenVisited[x][y]))) continue;

				if (x + 1 == n && y + 1 == m) {
					System.out.println(cur.moves + 1);
					return;
				}

				XY newXY = new XY(x, y, cur.moves + 1, cur.isBroken);

				if (cur.isBroken) {
					isBrokenVisited[x][y] = true;
				} else {
					isVisited[x][y] = true;
					if (arr[x][y] == 1)  {
						isBrokenVisited[x][y] = true;
						newXY.isBroken = true;
					}
				}

				queue.offer(newXY);
			}
		}

		System.out.println(-1);
	}

	private static class XY {
		int x;
		int y;
		int moves;
		boolean isBroken;

		public XY(int x, int y, int moves, boolean isBroken) {
			this.x = x;
			this.y = y;
			this.moves = moves;
			this.isBroken = isBroken;
		}
	}
}