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

1. 문제 요약

• N x M 행렬로 표현되는 지도가 있고, 각 좌표는 0과 1로 구성됩니다.
  • 0: 이동할 수 있는 곳
  • 1: 이동할 수 없는 벽
• 상하좌우 방향으로 이동할 수 있으며, 이동하는 중에 단 한 번만 벽을 부수고 이동할 수 있습니다.
• (1, 1)에서 시작해 (N, M)까지 가고자 할 때 최단 경로를 구하는 문제입니다.

입력 파라미터

• int N
• int M
• int[][] map

반환 타입

• int distance

예제

• N: 6
• M: 4
• map
  • 0100
  • 1110
  • 1000
  • 0000
  • 0111
  • 0000

주의 사항

• 최단 거리를 찾는 문제로 BFS를 사용해 풀 수 있습니다.
• 단, 방문 처리를 할 때 벽을 부쉈는지 여부를 함께 고려해줘야 합니다.

2. 문제 풀이

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;

public class Main {

  public static void main(String[] args) throws IOException {
    try (
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    ) {
      String[] NM = br.readLine().split(" ");
      int ROW = Integer.parseInt(NM[0]);
      int COL = Integer.parseInt(NM[1]);
      int[][] map = new int[ROW + 1][COL + 1];
      boolean[][][] isVisited = new boolean[ROW + 1][COL + 1][2];

      for (int row = 1; row <= ROW; row++) {
        char[] rowValues = br.readLine().toCharArray();
        for (int col = 1; col <= COL; col++) {
          map[row][col] = Character.getNumericValue(rowValues[col - 1]);
        }
      }

      int result = findShortestDistance(map, isVisited, ROW, COL);

      bw.write(String.valueOf(result));
    }
  }

  private static int findShortestDistance(int[][] map, boolean[][][] isVisited, int ROW, int COL) {
    Node node = new Node();
    int[] dRow = {1, 0, -1, 0};
    int[] dCol = {0, 1, 0, -1};
    Queue<Node> queue = new ArrayDeque<>();
    queue.offer(node);
    isVisited[node.row][node.col][node.cheatCount] = true;

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

      if (cur.row == ROW && cur.col == COL) {
        return cur.distance;
      }

      if (map[cur.row][cur.col] == 0) {
        for (int i = 0; i < 4; i++) {
          int row = cur.row + dRow[i];
          int col = cur.col + dCol[i];
          if (isInBound(row, col, ROW, COL) && !isVisited[row][col][cur.cheatCount]) {
            queue.offer(new Node(row, col, cur.distance + 1, cur.cheatCount));
            isVisited[row][col][cur.cheatCount] = true;
          }
        }
      } else {
        for (int i = 0; i < 4; i++) {
          int row = cur.row + dRow[i];
          int col = cur.col + dCol[i];
          if (cur.cheatCount == 0 && isInBound(row, col, ROW, COL) && !isVisited[row][col][0]) {
            queue.offer(new Node(row, col, cur.distance + 1, 1));
            isVisited[row][col][1] = true;
          }
        }
      }
    }

    return -1;
  }

  private static boolean isInBound(int row, int col, int ROW, int COL) {
    return 1 <= row && row <= ROW && 1 <= col && col <= COL;
  }

  static class Node {
    int row = 1;
    int col = 1;
    int distance = 1;
    int cheatCount = 0;

    public Node() {
    }

    public Node(int row, int col, int distance, int cheatCount) {
      this.row = row;
      this.col = col;
      this.distance = distance;
      this.cheatCount = cheatCount;
    }
  }

}

시간 복잡도

• BFS 탐색에 대한 시간복잡도
  • DFS/BFS 시간복잡도는 `O(노드 수 + 양방향 간선 수)`로 계산할 수 있습니다.
  • 지도의 노드 수는 `ROW x COL` 이고, 벽을 부쉈는지에 대한 경우의 수는 `2`가지입니다. 따라서 총 노드의 수는 `ROW x COL x 2` 입니다.
  • 최대 4개의 방향을 검사할 수 있으므로 간선 수는 `4 x 노드 수` = `8 x ROW x COL` 입니다.
• 시간 복잡도: `O(ROW X COL)`