[백준] 5427

불

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

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

class Queue {
  constructor() {
    this.head = new Node(-1);
    this.tail = new Node(-1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }
  enQueue(data) {
    let node = new Node(data);
    node.next = this.tail;
    node.prev = this.tail.prev;
    this.tail.prev.next = node;
    this.tail.prev = node;
    this.size++;
  }
  deQueue() {
    if (this.ifEmpty()) return -1;
    let tmp = this.head.next;
    tmp.next.prev = this.head;
    this.head.next = tmp.next;
    this.size--;
    return tmp.data;
  }
  ifEmpty() {
    return this.size ? false : true;
  }
}

const sangeunMove = (fireArr, sangeunArr, row, col, sangeunPos) => {
  let queue = new Queue();
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ];
  queue.enQueue(sangeunPos);
  sangeunArr[sangeunPos[0]][sangeunPos[1]] = 1;
  while (!queue.ifEmpty()) {
    let cur = queue.deQueue();
    for (let i = 0; i < 4; i++) {
      let coord = [cur[0] + dir[0][i], cur[1] + dir[1][i]];
      if (coord[0] < 0 || coord[0] >= col || coord[1] < 0 || coord[1] >= row)
        return sangeunArr[cur[0]][cur[1]];
      if (!(sangeunArr[coord[0]][coord[1]] === ".")) continue;
      if (sangeunArr[cur[0]][cur[1]] + 1 > fireArr[coord[0]][coord[1]])
        continue;
      sangeunArr[coord[0]][coord[1]] = sangeunArr[cur[0]][cur[1]] + 1;
      queue.enQueue([coord[0], coord[1]]);
    }
  }
  return "IMPOSSIBLE";
};

const fireMove = (fireArr, row, col) => {
  let queue = new Queue();
  let sangeun;
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ];
  for (let i = 0; i < col; i++) {
    for (let j = 0; j < row; j++) {
      if (fireArr[i][j] === "*") {
        queue.enQueue([i, j]);
        fireArr[i][j] = 0;
      } else if (fireArr[i][j] === "@") sangeun = [i, j];
    }
  }

  while (!queue.ifEmpty()) {
    let size = queue.size;
    for (let i = 0; i < size; i++) {
      let cur = queue.deQueue();
      for (let j = 0; j < 4; j++) {
        let coord = [cur[0] + dir[0][j], cur[1] + dir[1][j]];
        if (coord[0] < 0 || coord[0] >= col || coord[1] < 0 || coord[1] >= row)
          continue;
        if (
          !(
            fireArr[coord[0]][coord[1]] === "." ||
            fireArr[coord[0]][coord[1]] === "@"
          )
        )
          continue;
        fireArr[coord[0]][coord[1]] = fireArr[cur[0]][cur[1]] + 1;
        queue.enQueue([coord[0], coord[1]]);
      }
    }
  }
  return sangeun;
};

const fire = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\\n");
  let len = parseInt(input[0]);
  let i = 1;
  let ans = [];
  while (len--) {
    let row = parseInt(input[i].split(" ")[0]);
    let col = parseInt(input[i].split(" ")[1]);
    i++;
    let fireArr = input.slice(i, i + col).map((n) => n.split(""));
    let sangeunArr = input.slice(i, i + col).map((n) => n.split(""));
    let sangeun = fireMove(fireArr, row, col);
    ans.push(sangeunMove(fireArr, sangeunArr, row, col, sangeun));
    i += col;
  }
  console.log(ans.join("\\n"));
};

fire();

반성회

불! 의 응용편

https://blog.chichoon.com/371 에서 테스트케이스를 여러 개 받느라 for문이 하나 더 추가된 형태이다