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

🔥 접근

초기 접근 (시간/메모리 초과)

1. 최단 거리를 구하는 문제이므로 BFS를 사용한다.
2. 모든 벽(1)을 하나씩 제거한 후, 매번 BFS를 돌린다.
3. BFS 실행 시에는 visited 배열에 각 위치의 이동 거리(step) 를 저장한다.
4. BFS가 끝난 후 visited[N-1][M-1]의 값이 0이 아니면, 도착한 것으로 간주하고 값을 수집한다.
5. 모든 벽 제거 케이스에 대해 결과를 모은 뒤:
   • 0을 제외한 값들 중 최소 거리를 반환하고,
   • 유효한 값이 없다면 -1을 반환한다.

문제점: 모든 벽에 대해 BFS를 반복 실행하므로 시간복잡도가 O(N² × BFS)가 되어시간 초과 / 메모리 초과가 발생했다.

 

---

 

최적화된 접근 (정답 통과)

1. 여전히 BFS를 사용하지만, 벽을 한 번 부술 수 있는 상태를 BFS 상태에 포함시킨다.
2. 방문 상태를 visited[x][y][break] 로 표현한다
   • break = 0 → 아직 벽을 안 부쉈을 때의 방문거리
   • break = 1 → 벽을 부쉈을 때의 방문거리
3. 큐에는 [x, y, isBreak] 형태로 값을 넣고, 현재 벽 부순 여부에 따라 다음 이동 조건을 분기한다.
   
   • 벽이 아닌 경우: 현재 상태(isBreak) 그대로 진행하며 방문 여부 체크
   • 벽인 경우:
     • isBreak === 0 → 아직 벽을 안 부쉈다면 부수고 이동 가능
     • isBreak === 1 → 이미 부순 경우이므로 더 이상 벽 통과 불가능
4. 최종적으로 visited[N-1][M-1]에 저장된 두 값 중 0이 아닌 값 중 최소값을 결과로 반환하고, 없다면 -1을 리턴한다.

 

🧑‍💻 코드

const fs = require('fs');

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const input = fs.readFileSync(filePath, 'utf8').toString().trim().split('\n');

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

const bfs = (N, M, graph) => {
  const queue = [[0, 0, 0]]; // x, y, isBreak
  let visited = Array.from(
    { length: N },
    () => Array.from({ length: M }, () => [0, 0]) // 벽을 안부순 거리, 벽을 부순 거리
  );
  visited[0][0][0] = 1;

  let head = 0;
  while (queue.length > head) {
    const [px, py, isBreak] = queue[head++];

    for (let dir = 0; dir < 4; dir++) {
      const mx = px + dx[dir];
      const my = py + dy[dir];

      if (mx < 0 || my < 0 || mx >= N || my >= M) continue;

      // 벽이 아니고 방문 안했을때
      if (graph[mx][my] === 0 && visited[mx][my][isBreak] === 0) {
        visited[mx][my][isBreak] = visited[px][py][isBreak] + 1;
        queue.push([mx, my, isBreak]);
      }

      // 벽이면서 벽을 안부쉈고 방문 안했을때
      if (graph[mx][my] === 1 && !isBreak && visited[mx][my][1] === 0) {
        visited[mx][my][1] = visited[px][py][0] + 1;
        queue.push([mx, my, 1]);
      }
    }
  }

  const answer = visited[N - 1][M - 1].filter((v) => v !== 0);
  return answer.length ? Math.min(...answer) : -1;
};

const [N, M] = input.shift().split(' ').map(Number);
const graph = input.map((item) => item.split('').map(Number));
console.log(bfs(N, M, graph));

🔗 관련 링크

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