[백준/Java] 2206 - 벽 부수고 이동하기

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

문제

---

풀이

문제를 보면 최단 거리를 구해야 하기 때문에 BFS를 활용해서 풀어야 한다

하지만 벽을 부수고 이동할 수 있기 때문에 일반적인 BFS로는 풀 수 없다

따라서 벽을 부쉈는지 판단할 수 있는 상태를 하나 두어야 한다

 

일반적인 BFS와 같이 방문 배열을 선언하는데 3중 배열로 선언하는 것이다

`visited[x좌표][y좌표][벽을 부쉈는지 여부]`

벽을 부쉈는지 여부가 `0`이라면 벽을 부수지 않고 이동한 상태이고, `1`이라면 벽을 부수고 이동한 상태이다

 

사방 탐색을 진행하면서 벽이 없는 곳을 지나갈 때는 방문 여부만 확인하고 방문하지 않았다면 이동 거리를 갱신하지만

벽이 있는 곳을 지나갈 때는 현재 벽을 부쉈는지 확인하고 벽을 한번도 안 부쉈을 때만 지나갈 수 있게 한다

벽을 부수고 지나갔다면 다음부터는 벽을 부술 수 없으므로 벽을 부순 상태의 배열을 탐색해야 한다

배열이 끝나는 칸에 도달했으면 정답을 출력한다

 

자세한 것은 코드를 보자

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N, M;

	static int[][] arr;
	static int[][][] visited; // 3차원 방문 배열 (x좌표, y좌표, 벽을 부쉈는지 여부)

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N][M];
		visited = new int[N][M][2];
		// 0 -> 벽을 부수지 않고 도착한 상태
		// 1 -> 벽을 부수고 도착한 상태

		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j] = line.charAt(j) - '0';
			}
		}

		// 시작 지점 1로 초기화
		visited[0][0][0] = visited[0][0][1] = 1;

		int result = bfs(); // bfs 호출
		if (result == 0) {
			System.out.println(-1);
		} else {
			System.out.println(result);
		}

		br.close();
	}

	static int bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[]{0, 0, 0}); // 큐에 시작 지점 추가

		while (!queue.isEmpty()) {
			int[] current = queue.poll();
			int curX = current[0];
			int curY = current[1];
			int broken = current[2];

			// 현재 위치가 끝 위치라면 위치 배열 값 리턴
			if (curX == N - 1 && curY == M - 1) {
				return visited[curX][curY][broken];
			}

			for (int i = 0; i < 4; i++) {
				// 사방 탐색
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				// 이동한 좌표가 배열 범위 내에 있고
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M) {
					// 벽이 없다면
					if (arr[nextX][nextY] == 0) {
						// 방문하지 않았다면
						if (visited[nextX][nextY][broken] == 0) {
							visited[nextX][nextY][broken] = visited[curX][curY][broken] + 1; // 이동 거리 +1
							queue.add(new int[]{nextX, nextY, broken}); // 다음 좌표, 상태 큐에 추가
						}
					} else { // 벽이 있는 경우
						if (broken == 0) { // 벽을 한번도 안 부쉈을 때만 이동 가능
							if (visited[nextX][nextY][1] == 0) { // 방문하지 않았다면
								visited[nextX][nextY][1] = visited[curX][curY][broken] + 1; // 이동 거리 +1
								// 다음 좌표, 상태 큐에 추가 (벽을 부쉈으니 이후에는 항상 1로 넘김)
								queue.add(new int[]{nextX, nextY, 1});
							}
						}
					}
				}
			}
		}
		return 0;
	}

}

결과