문제

https://www.acmicpc.net/problem/5427
보드가 주어지고 벽과 상근이와 불의 위치가 주어진다.
1. 1초가 지날때마다 불은 👆, 👇, 👈, 👉 빈곳으로 번진다.
2. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다.
3. 상근이는 벽을 통과할 수 없다.
4. 상근이는 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.
5. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

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

풀이 1

보자마자 bfs로 풀어야 하는건 알겠는데 어떻게 해야할지 잠깐 고민했다.
그러고서 처음 생각난 방법은 지도에 불이 번진 시간을 기록해둔다음에
보드에 표시된 시간이 현재 시간보다 클경우 (아직 불이 번지기 전일경우) 이동하도록 했다.

코드 1

class Queue {
  l = 0;
  r = 0;
  q = {};
  isEmpty() {
    return this.l === this.r;
  }
  push(data) {
    this.q[this.r++] = data;
  }
  pop() {
    if (this.isEmpty()) return undefined;
    const result = this.q[this.l];
    delete this.q[this.l++];
    return result;
  }
}

const stdin = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
const input = (() => { let l = 0; return (isStr) => stdin[l++].split(isStr ? '': ' ')})();

const next = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

const isGoal = (h, w, y, x) => y < 0 || y >= h || x < 0 || x >= w;
const isInBoard = (h, w, y, x) => y >= 0 && y < h && x >= 0 && x < w;
const getNowPos = (board, h, w) => {
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (board[i][j] === '@') {
        return [i, j];
      }
    }
  }
};
const getFiredBoard = (board, h, w) => {
  const fireQ = new Queue();

  // 최초 불 위치 큐에 넣음
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (board[i][j] === '*') {
        fireQ.push([i, j, 0]);
      }
    }
  }

  while (!fireQ.isEmpty()) {
    const [y, x, cnt] = fireQ.pop();

    for (const [yy, xx] of next) {
      const [ny, nx] = [y + yy, x + xx];
      // 보드밖이면 불이 이동 못함
      if (!isInBoard(h, w, ny, nx)) continue;
      if (board[ny][nx] !== '.') continue;

      board[ny][nx] = cnt + 1;
      fireQ.push([ny, nx, cnt + 1]);
    }
  }

  return board;
};

const solution = (board, h, w) => {
  const [py, px] = getNowPos(board, h, w);
  const visited = Array.from({ length: h }, () => Array.from({ length: w }, () => false));
  // 불을 bfs로 옮김.
  // 만약 빈 공간일 경우에만 옮길 수 있음.
  const firedBoard = getFiredBoard(board, h, w);
  const playerQueue = new Queue();

  playerQueue.push([py, px, 0]);
  visited[py][px] = true;
  // 플레이어는 보드에서 현재 숫자보다 큰곳(나중에 불 붙을곳)으로만 이동할 수 있음.

  while (!playerQueue.isEmpty()) {
    const [y, x, time] = playerQueue.pop();
    if (isGoal(h, w, y, x)) return time;

    for (const [yy, xx] of next) {
      const [ny, nx] = [y + yy, x + xx];

      if (isGoal(h, w, ny, nx)) return time + 1;

      if (visited[ny][nx]) continue;

      if (firedBoard[ny][nx] > time + 1 || firedBoard[ny][nx] === '.') {
        playerQueue.push([ny, nx, time + 1]);
        visited[ny][nx] = true;
      }
    }
  }ㅌ
  return 'IMPOSSIBLE';
};

const T = +input();
for (let test = 0; test < T; test++) {
  const [w, h] = input().map(Number);
  const board = Array.from({ length: h }, () => input(true));
  const result = solution(board, h, w);
  console.log(result);
}

풀이 2

위 코드는 생각한데로 코드가 작동해줬고 한번에 정답을 맞췄다.
그런데 다른 사람보다 속도가 많으면 2배가 차이나서 조금더 최적화 할 수 없을까? 생각해봤다.

처음에는 큐를 두개 사용해서 따로따로 돌려줘야 한다고 생각했다.
그래야 불을 번지게 하고 -> 상근이를 움직여 줄 수 있다고 생각했기 떄문이다.

그런데 다시 생각해보면 그럴 필요가 없었다.
처음에 큐에 넣어줄 때 불을 모두 넣고 상근이를 넣는다면
항상 해당 시간에 불이 다 번진다음 상근이가 마지막으로 나오기 때문이다.

결론은 큐를 하나만 써서 bfs 탐색을 일반적으로 해도 된다는 소리였다.

그리고 큐에 넣은게 상근이인지 불인지 구분을 해야 할 때가 있다.
불은 밖으로 못번지지만 상근이는 밖으로 나갈 수 있기 떄문이다.
그래서 time을 -1과 1 이상의 값으로 구분을 해주며 불이 밖으로 번지는걸 막아줬다.
만약 -1이 아니라 1 이상의 값이 들어가 있으면 그건 상근이가 성공적으로 탈출을 한거다.
이때 time+1를 리턴해주면 된다.

정답 2

class Nodee {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}
class Queue {
  head;
  tail;
  isEmpty() {
    return this.head ? false : true;
  }
  push(data) {
    const node = new Nodee(data, null);
    if (this.head) this.tail.next = node;
    else this.head = node;

    this.tail = node;
  }
  pop() {
    if (!this.head) return undefined;
    const result = this.head.value;
    this.head = this.head.next;
    return result;
  }
}

const stdin = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
const input = (() => { let l = 0; return (isStr) => stdin[l++].split(isStr ? '': ' ')})();

const next = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

const isGoal = (h, w, y, x) => y < 0 || y >= h || x < 0 || x >= w;

const insertQueue = (board, q, h, w) => {
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (board[i][j] === '*') q.push([i, j, -1]);
    }
  }
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (board[i][j] === '@') q.push([i, j, 0]);
    }
  }
};

const solution = (board, h, w) => {
  const q = new Queue();

  insertQueue(board, q, h, w);

  while (!q.isEmpty()) {
    const [y, x, time] = q.pop();

    for (const [yy, xx] of next) {
      const [ny, nx] = [y + yy, x + xx];
      if (isGoal(h, w, ny, nx)) {
        if (time < 0) continue;
        return time + 1;
      }
      if (board[ny][nx] !== '.') continue;
      board[ny][nx] = 'X';
      q.push([ny, nx, time < 0 ? -1 : time + 1]);
    }
  }
  return 'IMPOSSIBLE';
};
const T = +input();
for (let test = 0; test < T; test++) {
  const [w, h] = input().map(Number);
  const board = Array.from({ length: h }, () => input(true));
  const result = solution(board, h, w);
  console.log(result);
}