[백준] 4179번: 불! - Node.js (자바스크립트)

1. 문제 ㅡ 4179번: 불! (난이도: Gold IV)

4179번: 불!

2. 풀이 ㅡ Node.js (자바스크립트)

class Queue {
  constructor() {
    this.q = [];
    this.head = 0;
    this.tail = 0;
  }

  push(item) {
    this.q[this.tail++] = item;
  }

  shift() {
    this.head++;
  }

  front() {
    return this.q[this.head];
  }

  isEmpty() {
    return this.head === this.tail;
  }
}

const [info, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [Y, X] = info.split(' ').map(val => +val);
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const fireRoute = input.map(row => [...row]);

const getFireSpreadTimes = () => {
  const checked = Array.from({ length: Y }).map(_ => Array.from({ length: X }, () => false));
  const fires = new Queue();

  for (let y = 0; y < Y; y++) {
    for (let x = 0; x < X; x++) {
      if (fireRoute[y][x] !== 'F') continue;

      fires.push([x, y, 0]);
      checked[y][x] = true;
    }
  }

  while (!fires.isEmpty()) {
    const [x, y, time] = fires.front();
    fires.shift();

    fireRoute[y][x] = time;

    for (let i = 0; i < 4; i++) {
      const dir = dirs[i];

      const xPos = x + dir[0];
      const yPos = y + dir[1];

      if (xPos < 0 || yPos < 0 || xPos >= X || yPos >= Y || checked[yPos][xPos] || fireRoute[yPos][xPos] === '#')
        continue;

      fireRoute[yPos][xPos] = time + 1;
      checked[yPos][xPos] = true;
      fires.push([xPos, yPos, time + 1]);
    }
  }
};

const getEscapeTime = () => {
  getFireSpreadTimes();

  const checked = Array.from({ length: Y }).map(_ => Array.from({ length: X }, () => false));

  for (let x = 0; x < X; x++) {
    for (let y = 0; y < Y; y++) {
      if (input[y][x] !== 'J') continue;

      const queue = new Queue();
      queue.push([x, y, 0]);

      while (!queue.isEmpty()) {
        const [x, y, time] = queue.front();
        queue.shift();

        for (let i = 0; i < 4; i++) {
          const dir = dirs[i];

          const xPos = x + dir[0];
          const yPos = y + dir[1];

          if (xPos < 0 || yPos < 0 || yPos >= Y || xPos >= X) return time + 1;

          if (checked[yPos][xPos] || fireRoute[yPos][xPos] === '#' || fireRoute[yPos][xPos] <= time + 1) continue;

          checked[yPos][xPos] = true;
          queue.push([xPos, yPos, time + 1]);
        }
      }
    }
  }

  return 'IMPOSSIBLE';
};

console.log(getEscapeTime());

 

2-1. 풀이 설명

BFS를 두 번 돌리는 게 핵심인 문제다. (불과 지훈이를 동시에 이동시키려고 하면 훨씬 복잡해짐)

 

1. 첫 번째 BFS에서는 불의 시작점을 기준으로 불이 번지는 시간을 기록해둔다. 불은 1분에 좌우상하로 한 칸씩 번지므로 좌표와 시간 + 1 값을 넣어주고, 각 칸의 값을 시간으로 바꿔주면 추후 지훈이가 갈 수 있는 칸과 없는 칸을 구분하기 쉽다. 여기서 가장 중요한 건 불이 여러 곳에서 시작될 수 있다는 점이다. 불의 시작점을 모두 찾아서 큐에 넣어준 후 while문을 돌아야 문제를 통과할 수 있다. 
2. 두 번째 BFS에서는 지훈이의 움직임을 파악하면 된다. 벽, 즉 '#'이 아닌 칸은 이제 모두 불에 붙는 시간으로 값이 변경되어 있다. 지훈이의 위치를 기준으로 지훈이가 이동할 수 있는 칸, 즉 좌우상하에 위치한 칸 중 값이 지훈이가 불보다 먼저 도착할 수 있는 칸의 좌표와 시간 + 1 값을 큐에 담아주며 while문을 돌면 된다. 만약 지훈이의 위치가 미로의 끝이라면 현재까지 누적된 시간 + 1을 반환해주면 된다. 반대로 while문이 끝났는데 지훈이가 탈출하지 못했다면 'IMPOSSIBLE' 문자열을 반환해주면 된다.

 

2-2. 회고

문제에서 주어진 테스트 케이스에서는 'J'와 'F'가 각각 하나씩 있으므로 지훈이도 불의 시작점도 하나씩 있다고 착각할 수 있지만, 이 문제에서는 불이 여러 군데에서 시작할 수 있다는 점을 명심해야 한다.  

 

풀기 전 분명 J는 입력에서 하나만 주어진다라고 명시되어 있는 걸 봤지만, "설마 이래놓고 F는 여러 개 있진 않겠지?" 라고 생각하며 문제를 풀기 시작했고, 결국 문제를 푸는 도중 이런 생각을 했다는 것 자체를 아예 까먹었다. (덕분에 너무 많은 시간을 낭비했다)