문제

이해

0과 1로 이루어진 NxM의 보드가 있다.

0은 이동가능함을 의미하고 1은 벽으로 이동이 불가능하다.

상하좌우로 움직일 수 있는 말을 (1, 1)에서 (N, M)까지 이동하려 할 때 최소이동거리를 구하여라.

단, 벽은 단 한 번 부술 수 있다.

접근

처음에는 단순 BFS를 생각했다. 이차원 배열 visited를 통해 방문 여부를 검사하고 목적지까지의 최소거리를 구하였다.

이 때, 벽의 처리는 이전에 벽을 부수지 않았다면 부수고 나아가는 식으로 처리했다.

하지만 위 풀이에는 오류가 존재한다.

예를 들어, 목적지까지 도달하려면 특정한 벽을 하나 무조건 부숴야 하는 보드가 있다고 하자.

탐색 중에 다른 벽을 만나 부쉈다면 당연하게도 목적지 앞의 벽은 부수지 못한다.

만일 그 다음 탐색 중에서 벽을 부수지 않고 특정한 벽까지 도달했다면?

위 풀이처럼 이차원 배열의 visited로 방문여부를 체크하면 이전에 불가능한 경우 탐색에서 한번 방문했기 때문에 벽을 부수기 이전에 방문하지도 못한다.

따라서, visited를 벽을 부쉈는지 조사하기 위해 3차원 배열로 선언할 필요가 있다.

visited[2][N][M]로 선언하여 visited[0][N][M]은 벽을 부수지 않았을 때 방문여부,
visited[1][N][M]은 벽을 부쉈을 때 방문여부를 체크한다.

다음은 BFS 내부의 분기문의 내용이다.

• 이전에 벽을 부쉈다
  • 다음 공간이 1
    • 불가능
  • 다음 공간이 0
    • 가능 (visited[1][x][y]에 방문여부 기록)

• 이전에 벽을 부수지 않았다
  • 다음 공간이 1
    • 가능 (벽 부숨 여부를 기록하고 visited[1][x][y]에 방문여부 기록)
  • 다음 공간이 0
    • 가능 (visited[0][x][y]에 방문여부 기록)

코드

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob2206 {
  static int N;
  static int M;
  static int[][] board;
  static boolean[][][] visited;
  static int[] d_row = { -1, 0, 1, 0 };
  static int[] d_col = { 0, 1, 0, -1 };
  static int min = Integer.MAX_VALUE;

  static class xy {
    int x;
    int y;
    int cnt;
    boolean crash_wall;

    public xy(int x, int y, int cnt, boolean crash_wall) {
      this.x = x;
      this.y = y;
      this.cnt = cnt;
      this.crash_wall = crash_wall;
    }
  }

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

    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    board = new int[N][M];
    visited = new boolean[2][N][M];

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

    bfs();

    if (min == Integer.MAX_VALUE) {
      System.out.println(-1);
    } else
      System.out.println(min);
  }

  static void bfs() {
    Queue<xy> q = new LinkedList<>();
    q.add(new xy(0, 0, 1, false));
    visited[0][0][0] = true;

    while (!q.isEmpty()) {
      xy now = q.poll();

      if (now.x == N - 1 && now.y == M - 1) {
        min = now.cnt;
        return;
      }

      for (int i = 0; i < 4; i++) {
        int new_x = now.x + d_row[i];
        int new_y = now.y + d_col[i];
        if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= M) {
          continue;
        }

        if (now.crash_wall) {
          if (board[new_x][new_y] == 0 && !visited[1][new_x][new_y]) {
            visited[1][new_x][new_y] = true;
            q.add(new xy(new_x, new_y, now.cnt + 1, true));
          }
        } else {
          if (board[new_x][new_y] == 1) {
            visited[1][new_x][new_y] = true;
            q.add(new xy(new_x, new_y, now.cnt + 1, true));
          } else if (!visited[0][new_x][new_y]) {
            visited[0][new_x][new_y] = true;
            q.add(new xy(new_x, new_y, now.cnt + 1, false));
          }
        }
      }
    }
  }
}

결과

방문여부를 따로 체크해야하기 때문에 까다로운 문제인 것 같다.