[BOJ] 5427: 불 / JS

문제: https://www.acmicpc.net/problem/5427

 

 

 

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const n = Number(input.shift());

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

let visit;

let h, w;

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

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

  push(data) {
    const node = new Node(data);
    this.tail.next = node;
    this.tail = node;
    this.size++;
  }

  shift() {
    if (this.size === 0) return;
    const node = this.head.next;
    if (node === this.tail) this.tail = this.head;
    this.head.next = node.next;
    this.size--;
    return node.data;
  }
  getSize() {
    return this.size;
  }
}

let fireQ;
let escapeQ;

function isRange(x, y) {
  return x >= 0 && x < h && y >= 0 && y < w;
}

function bfs() {
  while (fireQ.getSize() || escapeQ.getSize()) {
    for (let i = fireQ.getSize(); i > 0; i--) {
      const [x, y] = fireQ.shift();
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (!isRange(nx, ny) || visit[nx][ny] === 1) continue;
        fireQ.push([nx, ny]);
        visit[nx][ny] = 1;
      }
    }

    for (let i = escapeQ.getSize(); i > 0; i--) {
      const [x, y, d] = escapeQ.shift();
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (!isRange(nx, ny)) return d + 1;
        if (visit[nx][ny]) continue;
        escapeQ.push([nx, ny, d + 1]);
        visit[nx][ny] = 2;
      }
    }
  }
  return 'IMPOSSIBLE';
}

function soluition() {
  const answer = [];

  for (let t = 0; t < n; t++) {
    fireQ = new Queue();
    escapeQ = new Queue();
    [w, h] = input.shift().split(' ').map(Number);

    const map = [];
    for (let i = 0; i < h; i++) map.push(input.shift().trim().split(''));

    visit = new Array(h);
    for (let i = 0; i < h; i++) visit[i] = Array.from({ length: w }, () => 0);

    for (let i = 0; i < h; i++) {
      for (let j = 0; j < w; j++) {
        if (map[i][j] === '*') {
          fireQ.push([i, j, 0]);
          visit[i][j] = 1;
        } else if (map[i][j] === '@') {
          escapeQ.push([i, j, 0]);
          visit[i][j] = 2;
        } else if (map[i][j] === '#') visit[i][j] = 1;
      }
    }
    answer.push(bfs());
  }
  console.log(answer.join(' '));
}
soluition();

불의 이동을 따라가는 큐와 상근이의 탈출 경로를 추적하는 큐 두 개를 만들어서 해결했다.

map은 문제에서 주어진 빌딩의 지도고, visit은 방문 여부를 체크하기 위한 배열이다.

 

solution 함수에서 map을 순회하면서 *은 fireQ에 넣을뿐만 아니라 visit을 1로 업데이트한다.

@은 escapeQ에 push하고, 불과 구분하기 위해서 visit을 2로 변경한다.

#도 마찬가지로 불과 상근이가 접근하는 것을 방지하기 위해 visit을 1로 변경한다.

초기 세팅이 완료된 후 bfs 함수를 호출한다.

 

bfs 함수는 fireQ와 escapeQ를 동시에 처리한다.

불의 이동은 현재 fireQ에 들어있는 요소의 개수만큼 front를 하나씩 꺼내서 아래 과정을 동시에 처리하면 된다.

  => 큐 안에 있는 요소들을 동시에 처리하는 이유는 1초마다 불이 번지고, 상근이가 이동하는 시간의 흐름에 맞게 처리하기 위해서다.

 

상, 하, 좌, 우로 이동할 수 있는지 확인하기 위해 nx, ny를 새롭게 구하고 올바른 영역안에 있는지와 visit을 확인한다.

조건문을 통과하면 fireQ에 [nx, ny]를 push하고 visit도 1로 체크해준다.

 

fireQ에 대한 처리가 끝났으면 상근이의 이동 경로에 대한 처리를 해야한다.

escapeQ도 마찬가지로 현재 큐에 들어있는 모든 요소에 대해서 동시에 처리해야 한다.

따라서 큐 사이즈만큼 아래의 과정을 반복해야 한다.

 

일단 이 문제의 목표는 상근이의 빌딩 탈출이기 때문에 (nx, ny)가 map의 범위를 벗어났다면

탈출했다는 의미이므로 지금까지 누적한 d에 1을 더한 값을 반환한다.

map을 아직 탈출하지 못했다면 visit을 체크하고 누구도 지나지 않은 길이라면 escapeQ에 push한다.

이때 상근이가 지나갔다는 것을 표시해주기 위해 visit을 2로 변경한다.

 

상근이가 무사히 빌딩을 탈출했다면 반복문 중간에서 d +1을 반환할 것이고,

탈출하지 못했다면 while문 밖으로 빠져나와서 "IMPOSSIBLE"을 반환할 것이다.

 

 

 

나는 큐를 두 개를 만들어서 해결했지만, 나중에 알고보니 큐 하나에 불과 상근이의 위치를 한꺼번에 넣고 해결할 수 있었다.

큐에 불의 위치를 먼저 넣고 마지막에 상근이의 위치를 넣어서 BFS를 처리하면 

현재 시간에 대한 불의 이동 경로를 먼저 처리한 후 상근이의 탈출 경로를 처리할 수 있어서

각 시간대별로 불과 상근이의 이동 경로를 동시에 해결할 수 있게 된다.