[백준 2206 - Node.js] 벽 부수고 이동하기

🔗 문제 링크

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

2206번: 벽 부수고 이동하기

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const map = input.slice(1).map(row => row.split('').map(Number));
const offset = [[0, 1], [1, 0], [-1, 0], [0, -1]];

class Node {
  constructor(x, y, isWallBroken) {
    this.prev = null;
    this.next = null;
    this.x = x;
    this.y = y;
    this.isWallBroken = isWallBroken;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(x, y, isWallBroken) {
    const node = new Node(x, y, isWallBroken);
    if (!this.size) {
      this.front = node;
      this.rear = node;
    } else {
      this.rear.next = node;
      node.prev = this.rear;
      this.rear = node;
    }
    this.size++;
  }

  dequeue() {
    if (!this.size) {
      return null;
    }

    const node = this.front;
    if (this.size === 1) {
      this.front = null;
      this.rear = null;
    } else {
      this.front = node.next;
      this.front.prev = null;
    }
    this.size--;
    return node;
  }
}

const bfs = () => {
  const visited = [...Array(N)].map(() => [...Array(M)].map(() => [0, 0]));
  visited[0][0] = [1, 0];
  const queue = new Queue();
  queue.enqueue(0, 0, 0);
  while (queue.size) {
    const { x, y, isWallBroken } = queue.dequeue();
    if (x === N - 1 && y === M - 1) {
      return visited[x][y][isWallBroken];
    }
    
    for (let i = 0; i < 4; i++) {
      const nx = x + offset[i][0];
      const ny = y + offset[i][1];
      if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
        if (!map[nx][ny] && !visited[nx][ny][isWallBroken]) {
          visited[nx][ny][isWallBroken] = visited[x][y][isWallBroken] + 1;
          queue.enqueue(nx, ny, isWallBroken);
        } else if (map[nx][ny] && !isWallBroken) {
          visited[nx][ny][1] = visited[x][y][0] + 1;
          queue.enqueue(nx, ny, 1);
        }
      }
    }
  }
  return -1;
}

console.log(bfs());

벽을 한 개만 부수면 되므로, 처음에는 모든 맵을 순회하면서 벽을 한 개씩 미리 부순 상태에서 BFS를 실행하였더니 시간 초과가 났다. 왜냐하면 시간복잡도가 O((NM)^2) 이기 때문에 최대 1000^4(1조)번의 연산이 필요하기 때문이다.

 

그래서 이 문제는 탐색을 하면서 해당 칸에 도달할 때까지 벽을 부순 적이 있는지 여부를 저장하고, 방문 여부를 벽을 부수지 않고 온 경우와 부수고 온 경우를 각각 나눠서 기록해야 한다.

 

먼저, 방문 여부(visited)는 맵과 같은 크기로 만들되, 각 칸에 [0, 0]을 넣어서 벽을 부수지 않고 방문 여부, 벽을 부수고 방문 여부를 동시에 기록한다.

 

queue에는 x좌표, y좌표, 해당 좌표에 도달할 때까지 벽을 부순 적이 있는지 여부를 0과 1로 나타낸 정보를 담는다.

 

상하좌우 4방향에서 좌표의 유효성 검사를 통과한 후, 두 가지 경우로 나뉜다.

 

1. 다음 칸이 벽이 아닌 경우

벽을 부순 적이 없다면 visited[nx][ny][0]의 방문 여부를 확인하고, 방문하지 않았을 때 queue에 nx, ny, 0의 정보를 담는다. 그리고 다음 칸의 방문 여부는 벽을 부순 적이 없을 때의 방문 여부를 갱신한다.

벽을 부순 적이 있다면 visited[nx][ny][1]의 방문 여부를 확인하고, 방문하지 않았을 때 queue에 nx, ny, 1의 정보를 담는다. 그리고 다음 칸의 방문 여부는 벽을 부순 적이 있을 때의 방문 여부를 갱신한다.

이걸 isWallBroken이 0 또는 1이라는 점과 visited[nx][ny]에 길이가 2인 배열로 방문 여부를 저장한다는 점을 이용하여 두 가지 경우로 분기하지 않고 한 번에 처리할 수 있었다.

 

2. 다음 칸에 벽이 있고, 아직까지 벽을 부순 적이 없는 경우

queue에 nx, ny, 1의 정보를 담고, 다음 칸의 벽을 부순 적이 있을 때의 방문 여부를 갱신한다.

 

방문 여부를 단순히 true, false로 하지 않고 숫자로 나타낸 이유는 현재까지 이동한 칸 수를 visited에 저장하기 위해서다. 방문 여부를 갱신할 때 이전 칸의 visited를 참고하여 1을 더한 값으로 갱신하였다.

 

최종적으로 목표한 칸에 도달하면 visited에 저장된 현재까지 이동한 칸 수를 반환하고, while문을 빠져나오면 목표한 칸까지 도달하지 못한 것이므로 -1을 반환하였다.

 

 

✏️ 다른 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const map = input.slice(1).map(row => row.split('').map(Number));
const offset = [[0, 1], [1, 0], [-1, 0], [0, -1]];

const bfs = () => {
  const visited = [...Array(N)].map(() => [...Array(M)].map(() => [0, 0]));
  visited[0][0] = [1, 0];
  let queue = [];
  let stack = [];
  queue.push([0, 0, 0]);
  
  while (queue.length) {
    stack = queue;
    queue = [];
    
    while (stack.length) {
      const [ x, y, isWallBroken ] = stack.pop();
      
      if (x === N - 1 && y === M - 1) {
        return visited[x][y][isWallBroken];
      }
      
      for (let i = 0; i < 4; i++) {
        const nx = x + offset[i][0];
        const ny = y + offset[i][1];
        if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
          if (!map[nx][ny] && !visited[nx][ny][isWallBroken]) {
            visited[nx][ny][isWallBroken] = visited[x][y][isWallBroken] + 1;
            queue.push([nx, ny, isWallBroken]);
          } else if (map[nx][ny] && !isWallBroken) {
            visited[nx][ny][1] = visited[x][y][0] + 1;
            queue.push([nx, ny, 1]);
          }
        }
      }
    }
  }
  return -1;
}

console.log(bfs());

처음에는 시간 초과 때문에 Queue를 직접 구현하여 풀었다. BFS를 할 때 queue를 배열로 만들어서 사용하면 shift 연산(시간복잡도 O(n))을 하는 것 때문에 시간 초과가 날 확률이 높기 때문이다. 그런데, 배열을 사용하고도 Queue를 직접 구현한 것보다 더 시간이 적게 걸리는 방법(항상 빠른지는 알 수 없음)을 찾았다.

 

현재 상태의 queue 내용물을 그대로 갖는 stack을 이용해서 인접 노드를 순회하고, 새롭게 인접 노드들을 추가할 때에는 빈 queue에 추가하는 방식이다. 

 

기존의 방식으로는 queue에서 하나씩 shift하면서 그 shift된 노드의 인접 노드들을 queue에 전부 push하는 방식이었다. 그런데, push된 인접 노드들은 같은 depth라면 꼭 원래 순서대로 순회해야할 필요는 없다. 그래서 한 번에 추가된 같은 depth의 인접 노드들 전체를 스택에 담고 스택을 pop(시간복잡도 O(1))하는 방식으로 거꾸로 순회하며 시간을 줄이고, 그 인접 노드들에서 새로 추가되는 인접 노드들은 빈 queue에 push한다.

 

stack에는 같은 depth의 인접 노드들이 들어가기 때문에 다른 depth인 노드끼리 순서가 뒤바뀔 염려가 없다.

 

Queue 자료 구조를 지원하지 않는 자바스크립트로 BFS를 풀 때 유용한 방법인 것 같다. 그 동안 Queue를 직접 구현하느라 불편했는데, 이 방법을 자주 사용할 것 같다.