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

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

✅ 문제 설명

🧐 첫 번째 접근

• 문제를 읽고 바로 떠오른 방법은 벽을 안 부수고 목표지점까지 가는 경로와 모든 벽을 한 번씩 다 부수고 목표지점까지의 경로들을 전부 구해서 최소값을 통해 해결하려고 했다.
  but, 시간초과

const fs = require("fs");
let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const [N, M] = input.shift().split(" ").map(Number);
const graph = input.map((line) => line.trim().split("").map(Number));
const bfs = (startX, startY) => {
  const queue = [[startX, startY]];
  const visited = Array.from({ length: N }, () => Array(M).fill(false));
  visited[startX][startY] = true;
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  let distance = 0;
  while (queue.length) {
    const size = queue.length;
    distance++;
    for (let i = 0; i < size; i++) {
      const [x, y] = queue.shift();
      if (x === N - 1 && y === M - 1) {
        return distance;
      }
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
          if (graph[nx][ny] === 0 && !visited[nx][ny]) {
            visited[nx][ny] = true;
            queue.push([nx, ny]);
          }
        }
      }
    }
  }
  return -1;
};
let answer = bfs(0, 0);
let minDistance = answer === -1 ? Infinity : answer;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (graph[i][j] === 1) {
      graph[i][j] = 0;
      const result = bfs(0, 0);
      if (result !== -1) {
        minDistance = Math.min(minDistance, result);
      }
      graph[i][j] = 1;
    }
  }
}
console.log(minDistance === Infinity ? -1 : minDistance);

✅ 개선한 부분

• BFS를 한 번만 호출하여 각 위치에서 벽을 부수는 경우와 부수지 않는 경우를 모두 처리
  • 벽을 부수는 경우의 수를 따로 처리하지 않기 때문에 시간 복잡도가 개선된다.
• 어떻게?
  • 기존 visited 배열에는 방문 여부만 체크하기 때문에 2차원 배열로 구성되어 있었다.
  • 개선한 코드에서는 visited 배열을 3차원 배열로 바꾸고 배열에 isBreak라는 값을 통해 각 위치에서 벽을 부수었는지의 여부를 체크한다.
  ➡️ 벽을 부수는 상태를 따로 관리함으로써 중복 탐색을 방지하고 bfs 호출을 단순화 했다.

✅ 정답 코드

const fs = require("fs");

// 입력을 읽어오기
let input = fs
  .readFileSync("./20주차/김선구/input.txt")
  .toString()
  .trim()
  .split("\n");

// N, M 추출
let [N, M] = input[0].split(" ").map(Number);

input = input.slice(1).map((v) => v.split("").map(Number));

// 3차원 배열로 방문 여부를 기록, visited[y][x][isBreak]
// isBreak: 0이면 벽을 부수지 않은 상태, 1이면 벽을 부순 상태
const visited = Array.from(Array(N), () =>
  Array(M)
    .fill(0)
    .map(() => [0, 0]) // 각 위치에서 두 가지 상태를 기록
);

const dx = [1, 0, -1, 0]; 
const dy = [0, 1, 0, -1]; 
const q = []; 

q.push([0, 0, 0]); // 시작 위치 (0, 0)와 isBreak 상태(0) 추가
visited[0][0][0] = 1; // 시작 위치 방문 처리

function BFS() {
  let pointer = 0; // 큐의 포인터

  // 큐가 비어있지 않은 동안 반복
  while (pointer !== q.length) {
    // 현재 위치와 벽을 부순 여부 가져오기
    const [y, x, isBreak] = q[pointer];

    // 목표 지점에 도착했을 경우
    if (x === M - 1 && y === N - 1) {
      return visited[y][x][isBreak]; // 해당 위치에서의 거리 반환
    }

    // 네 방향 탐색
    for (let i = 0; i < dx.length; i++) {
      const [ny, nx] = [y + dy[i], x + dx[i]]; // 다음 위치 계산

      // 다음 위치가 그래프 범위 내에 있는지 확인
      if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
        // 다음 위치가 빈 공간(0)일 때
        if (input[ny][nx] === 0 && visited[ny][nx][isBreak] === 0) {
          visited[ny][nx][isBreak] = visited[y][x][isBreak] + 1; // 거리 업데이트
          q.push([ny, nx, isBreak]); // 큐에 추가
        } 
        // 다음 위치가 벽(1)이고 아직 벽을 부수지 않은 경우
        else if (input[ny][nx] === 1 && isBreak === 0) {
          visited[ny][nx][1] = visited[y][x][isBreak] + 1; // 거리 업데이트
          q.push([ny, nx, isBreak + 1]); // 큐에 추가 (isBreak 상태 증가)
        }
      }
    }
    pointer++; // 다음 위치로 이동
  }

  return -1; // 목표에 도달할 수 없는 경우 -1 반환
}

console.log(BFS()); // BFS 실행 결과 출력