BOJ_2206 : 벽 부수고 이동하기

👉 문제링크

2206번: 벽 부수고 이동하기

---

---

🔸 문제 분석 🔸

• N * M 행렬 맵에서 (1, 1)부터 (N, M) 까지 이동하는 최단거리를 구한다.
  • 인접한 상하좌우로 1칸씩 이동할 수 있다.
  • 이동할 수 있는 칸은 0, 벽은 1로 표시되는데, 1번 벽을 부수고 이동할 수 있다.
• 행렬에서 최단거리를 구하는 문제이므로 BFS를 사용한다.
  • 벽을 부수고 먼저 도착했었던 칸을 벽을 부수지 않고 도착했다면, 이어서 탐색해보아야 한다.
  • 벽을 부수지않고 먼저 도착했던 칸이면 더 탐색해볼 필요가 없다.
  • N == 1, M == 1 인 경우는 따로 예외처리가 필요하다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static class Point {
		int x, y;
		boolean flag;

		public Point(int x, int y, boolean flag) {
			this.x = x;
			this.y = y;
			this.flag = flag;
		}
	}

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

	public static void main(String[] args) throws IOException {
		// Input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] map = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			char[] chars = br.readLine().toCharArray();
			for (int j = 1; j <= M; j++) {
				map[i][j] = chars[j - 1] - '0';
			}
		}

		// BFS
		Queue<Point> que = new ArrayDeque<>();
		int[][] visited = new int[N + 1][M + 1]; // 0: 방문 X, 1: 벽부수고 방문, 2: 벽안부수고 방문

		que.add(new Point(1, 1, false));
		visited[1][1] = 1;

		int cnt = 1;

		while (!que.isEmpty()) {
			int size = que.size();

			for (int i = 0; i < size; i++) {
				Point point = que.poll();

				if (point.x == N && point.y == M)
					break;

				for (int j = 0; j < dx.length; j++) {
					int row = point.x + dx[j];
					int col = point.y + dy[j];
					if (0 < row && row <= N && 0 < col && col <= M) {
						// 벽인 경우
						if (map[row][col] == 1 && !point.flag) {
							visited[row][col] = 1;
							que.add(new Point(row, col, true));
						}
						// 벽이 아닌 경우
						if (map[row][col] == 0) {
							if (visited[row][col] == 0) {
								visited[row][col] = point.flag ? 1 : 2;
								que.add(new Point(row, col, point.flag));
							} else if (visited[row][col] == 1 && !point.flag) {
								visited[row][col] = 2;
								que.add(new Point(row, col, false));
							}
						}
					}
				}
			}
			cnt++;
			if (visited[N][M] > 0)
				break;
		}

		if (N == 1 && M == 1)
			cnt--;

		// Output
		if (visited[N][M] == 0)
			bw.write(Integer.toString(-1));
		else
			bw.write(Integer.toString(cnt));
		bw.flush();
	}
}

🔸 코드 해석 🔸

• BFS를 위해 좌표와 벽 부수기 사용 여부를 담은 Point 클래스를 사용했다.
• 방문체크는 int형 2차원 배열 visited를 사용했다.
  • 0 : 아직 방문하지 않음.
  • 1 : 벽을 부수고 방문했음.
  • 2 : 벽을 부수지 않고 방문했음.
• BFS의 while문에서 큐의 크기만큼 반복해서 이동 횟수를 일치시키며 계산했다.
• 4방탐색 이동에서 경우에 따라서 처리했다.
  • 벽을 만났는데 아직 벽부수기를 사용하지 않았으면, 일단 부수고 진행해본다.
  • 벽이 아닌 경우는 2 가지로 나눠서 처리한다.
    
    • 아직 방문하지 않은 칸이면 그대로 진행한다.
    • 벽을 부수고 방문했던 곳인데, 현재 벽을 부수지 않았다면 진행해본다.
      (다른 곳을 부수는게 더 최단거리일 수 있기 때문)
• N==1이고 M==1 일 때 예외처리로 cnt 를 -1한다.
• (N, M)에 방문했다면 cnt를, 아니라면 -1을 출력한다.

---

🔸 end 🔸

• 벽을 부수고 먼저 도착했더라도, 벽을 부수지 않고 도착한 시도를 이어서 탐색해야 하는게 중요 포인트였다.
• N==1 && M==1 인 경우는 문제를 분석하며 조심해야겠다고 생각했었는데, 코딩 후에 까먹고 테스트하지 않아서 1회 틀리게 되었다. 요즘 풀이 전략을 적지 않고 대충 풀이하게 되는데, 다시 꼼꼼하게 하는 습관을 들여야겠다.