[BOJ 2206] 벽 부수고 이동하기

문제

벽 부수고 이동하기

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

 

 

풀이

설명

출발점에서 도착점까지 가는 최단 거리를 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. 상하좌우 인접한 칸으로 이동 가능합니다.
2. 벽이 있는 경우, 최대 한 번 부수고 이동할 수 있습니다.

 

BFS를 이용해 해결할 수 있습니다.

 

거리 배열은 벽을 부순 횟수도 포함해야 하므로 3차원 배열로 만들 수 있습니다.

 

예시 코드

function solution() {
  const BREAK_LIMIT = 1;

  const [n, m] = input().split(" ").map(Number);
  const board = Array.from({ length: n }, () => input().split("").map(Number));
  const dx = [0, -1, 0, 1];
  const dy = [1, 0, -1, 0];
  const dist = Array.from({ length: n }, () =>
    Array.from({ length: m }, () => Array(BREAK_LIMIT + 1))
  );
  dist[0][0][0] = 1;
  const queue = new Queue();
  queue.enqueue([0, 0, 0]);

  while (!queue.isEmpty()) {
    const [cx, cy, w] = queue.dequeue();
    if (cx === n - 1 && cy === m - 1) return dist[cx][cy][w];

    for (let i = 0; i < 4; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (dist[nx][ny][w]) continue;

      if (board[nx][ny] === 0) {
        dist[nx][ny][w] = dist[cx][cy][w] + 1;
        queue.enqueue([nx, ny, w]);
      } else if (w < BREAK_LIMIT) {
        dist[nx][ny][w + 1] = dist[cx][cy][w] + 1;
        queue.enqueue([nx, ny, w + 1]);
      }
    }
  }

  return -1;
}