(Java) 백준 2206

백준 2206

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	192 MB	168427	45604	28455	23.977%

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

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

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

답안

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ2206 {
    static class Node {
        int row, col, step;
        boolean isWallBrakeUsed;
        public Node(int row, int col, int step, boolean isWallBrakeUsed) {
            this.row = row;
            this.col = col;
            this.step = step;
            this.isWallBrakeUsed = isWallBrakeUsed;
        }
    }

    static final int[] dRow = {-1, 0, 0, 1};
    static final int[] dCol = {0, -1, 1, 0};
    enum Board {
        BLANK, WALL
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int maxRow = Integer.parseInt(firstLine[0]);
        int maxCol = Integer.parseInt(firstLine[1]);
        Board[][] board = new Board[maxRow][maxCol];
        for (int i = 0; i < maxRow; i++) {
            String line = br.readLine();
            for (int j = 0; j < maxCol; j++) {
                board[i][j] = (line.charAt(j) == '1')? Board.WALL : Board.BLANK;
            }
        }
        int[][] bestSteps = new int[maxRow][maxCol];
        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxCol; j++) {
                bestSteps[i][j] = Integer.MAX_VALUE;
            }
        }
        int[][] bestStepsUsingWallBreak = new int[maxRow][maxCol];
        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxCol; j++) {
                bestStepsUsingWallBreak[i][j] = Integer.MAX_VALUE;
            }
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0, 1, false));
        while (!queue.isEmpty()) {
            Node current = queue.poll();

            if (current.isWallBrakeUsed && current.step < bestStepsUsingWallBreak[current.row][current.col]) {
                bestStepsUsingWallBreak[current.row][current.col] = current.step;
            } else if (!current.isWallBrakeUsed &&current.step < bestSteps[current.row][current.col]) {
                bestSteps[current.row][current.col] = current.step;
            } else {
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nextRow = current.row + dRow[i];
                int nextCol = current.col + dCol[i];
                if (nextRow < 0 || nextRow >= maxRow || nextCol < 0 || nextCol >= maxCol) {
                    continue;
                }
                if (board[nextRow][nextCol] == Board.WALL) {
                    if (current.isWallBrakeUsed) {
                        continue;
                    }
                    queue.offer(new Node(nextRow, nextCol, current.step + 1, true));
                    continue;
                }
                queue.offer(new Node(nextRow, nextCol, current.step + 1, current.isWallBrakeUsed));
            }
        }

        int result = Math.min(bestSteps[maxRow-1][maxCol-1], bestStepsUsingWallBreak[maxRow-1][maxCol-1]);
        if (result == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(result);
        }
    }
}

풀이

BFS를 이용해 최소 경로를 구했다. 이때, 벽을 부수는지에 대한 여부를 기록하는 것이 중요한 문제였기 때문에, BFS의 queue에 벽을 부수기 전인지, 벽을 부순 후에 진행하고 있는 것인지에 대한 정보를 함께 넣어주었다.

코드가 다소 길지만, 가장 중요한 부분인 아래부터 살펴보자.

  Queue<Node> queue = new LinkedList<>();
  queue.offer(new Node(0, 0, 1, false)); // board의 가장 왼쪽 위부터 시작
  while (!queue.isEmpty()) {
      Node current = queue.poll();

			// 벽 부수기를 사용한 경우에만, 해당 board 칸까지 도달하는 최소 거리 기록
      if (current.isWallBrakeUsed && current.step < bestStepsUsingWallBreak[current.row][current.col]) {
          bestStepsUsingWallBreak[current.row][current.col] = current.step;
      } 
      // 벽 부수기를 사용하지 않은 경우에만, 해당 board 칸까지 도달하는 최소 거리 기록
      else if (!current.isWallBrakeUsed &&current.step < bestSteps[current.row][current.col]) {
          bestSteps[current.row][current.col] = current.step;
      }
      // 최소 거리가 아닌 경우 더이상의 탐색 종료
      else {
          continue;
      }

      for (int i = 0; i < 4; i++) {
          int nextRow = current.row + dRow[i];
          int nextCol = current.col + dCol[i];
          // 인덱스 범위 validation
          if (nextRow < 0 || nextRow >= maxRow || nextCol < 0 || nextCol >= maxCol) {
              continue;
          }
          if (board[nextRow][nextCol] == Board.WALL) {
              if (current.isWallBrakeUsed) {
                  continue;
              }
              // 벽을 만났다면, 벽 부수기를 사용하지 않은 경우에만 벽을 부수고 진행한다.
              queue.offer(new Node(nextRow, nextCol, current.step + 1, true));
              continue;
          }
          // 벽이 아닌 칸을 만났다면, 벽 부수기 사용 여부에 상관 없이 진행한다.
          queue.offer(new Node(nextRow, nextCol, current.step + 1, current.isWallBrakeUsed));
      }
  }

int result = Math.min(bestSteps[maxRow-1][maxCol-1], bestStepsUsingWallBreak[maxRow-1][maxCol-1]);
if (result == Integer.MAX_VALUE) {
    System.out.println("-1");
} else {
    System.out.println(result);
}

위의 BFS 탐색을 모두 진행하면, bestSteps와 bestStepsUsingWallBreak 에는 각 칸에 도달하는 최단 거리가 저장된다. 두 배열의 $(N, M)$의 위치에 있는 값 중 최소값을 출력하면 되는데, 이때 만약 $(N,M)$에 도달하지 못하였다면 초기값으로 저장한 Integer.MAX_VALUE가 업데이트되지 않은 상태로 남아있으므로, 도달 가능 여부를 판단할 수 있다.

따라서, 이 풀이에서 중요 포인트는 다음과 같다.

1. BFS를 사용해 최단거리를 찾는다.
2. 탐색 과정에서 벽 부수기 여부를 저장하고, 이를 이용해 벽 칸을 만났을 경우 벽 부수기를 사용하지 않았다면 벽을 부술 수 있도록, 그리고 벽이 아닌 칸을 만났을 경우 진행할 수 있도록 처리한다.
3. 각 칸마다 최단 경로를 저장한다.
   1. 벽 부수기 여부에 따라 다른 저장 공간을 할당한다. overwrite된다면 벽을 부쉈는데도 부수지 않은 상태에서 기록된 값이 섞일 수 있기 때문이다.
   2. 최단 경로를 저장함으로써, cycle이 없도록(이미 방문한 칸에 되돌아가지 않도록) 한다.