[백준] 4179

불!

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 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 jihoonMove = (fireArr, jihoonArr, row, col, jihoonPos) => {
  let queue = new Queue();
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ];
  queue.enQueue(jihoonPos);
  jihoonArr[jihoonPos[0]][jihoonPos[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] >= row || coord[1] < 0 || coord[1] >= col) {
        console.log(jihoonArr[cur[0]][cur[1]]);
        return;
      }
      if (!(jihoonArr[coord[0]][coord[1]] === ".")) continue;
      if (jihoonArr[cur[0]][cur[1]] + 1 > fireArr[coord[0]][coord[1]]) continue;
      jihoonArr[coord[0]][coord[1]] = jihoonArr[cur[0]][cur[1]] + 1;
      queue.enQueue([coord[0], coord[1]]);
    }
  }
  console.log("IMPOSSIBLE");
};

const fireMove = (fireArr, row, col) => {
  let queue = new Queue();
  let jihoon;
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ];
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (fireArr[i][j] === "F") {
        queue.enQueue([i, j]);
        fireArr[i][j] = 0;
      } else if (fireArr[i][j] === "J") jihoon = [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] >= row || coord[1] < 0 || coord[1] >= col)
          continue;
        if (
          !(
            fireArr[coord[0]][coord[1]] === "." ||
            fireArr[coord[0]][coord[1]] === "J"
          )
        )
          continue;
        fireArr[coord[0]][coord[1]] = fireArr[cur[0]][cur[1]] + 1;
        queue.enQueue([coord[0], coord[1]]);
      }
    }
  }
  return jihoon;
};

const fire = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n");
  const row = parseInt(input[0].split(" ")[0]);
  const col = parseInt(input[0].split(" ")[1]);
  input.shift();
  let fireArr = input.map((n) => n.split(""));
  let jihoonArr = input.map((n) => n.split(""));
  const jihoon = fireMove(fireArr, row, col);
  jihoonMove(fireArr, jihoonArr, row, col, jihoon);
};

fire();

반성회

1. 미로의 행과 열 미리 저장하기

let input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const row = parseInt(input[0].split(" ")[0]);
const col = parseInt(input[0].split(" ")[1]);
input.shift();

미로 본체를 뜯어오기 위해 row와 col 값을 미리 저장해준다

split을 두번 호출하므로 비효율적일 수 있으나 일단 그려려니 한다

row와 col을 저장한 뒤, 첫 번째 줄은 필요없으므로 input.shift()를 통해 지워버린다

1. 미로를 문자 단위로 잘라서 배열에 저장

let fireArr = input.map((n) => n.split(""));
let jihoonArr = input.map((n) => n.split(""));

input.map을 두번 호출한 이유는 fireArr과 jihoonArr은 같은 주소를 가리키면 안 되므로 아예 별개의 값으로 저장하기 위함이다

fireArr을 만들어놓고 이중for문으로 깊은복사 하는 건 코드의 줄 수가 너무 늘어나서 이런 방법을 선택

1. 불이 움직이는 경로 먼저 BFS로 구하기 (& 지훈이 시작좌표)

const fireMove = (fireArr, row, col) => {
  let queue = new Queue(); //새로운 큐 선언
  let jihoon; //지훈이 시작점 담을 변수 선언
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ]; //상하좌우 가중치 저장
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) { //배열 전체 탐색
      if (fireArr[i][j] === "F") { //미로에서의 문자열이 F일 경우
        queue.enQueue([i, j]); //큐에 해당 좌표 저장
        fireArr[i][j] = 0; //불꽃이 여기까지 퍼지는 데 걸린 시간 저장
        //불의 시작점이므로 퍼지는데 걸린 시간은 0으로 시작
      } else if (fireArr[i][j] === "J") jihoon = [i, j];
      //지훈이의 좌표는 따로 변수에 저장
      //한 함수에서 지훈이의 좌표까지 같이 구하는 이유는 
      //지훈이 좌표 구한다고 따로 for문 돌리기에 줄낭비이기 때문
    }
  }
  while (!queue.ifEmpty()) { //큐가 빌 때까지 BFS 시작
    let size = queue.size; //현재 큐에 있는 모든 원소를 탐색하기 위해 우선 큐의 크기 저장
    //따로 저장하지 않으면 큐에서 deQueue 또는 상하좌우 좌표를 enQueue할 때마다 
    //사이즈가 변하기 때문
    for (let i = 0; i < size; i++) { //큐에 있는 모든 원소에 대하여 (이전 시점까지 큐에 저장한 원소들)
      let cur = queue.deQueue(); //큐에서 원소 하나 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] >= row || coord[1] < 0 || coord[1] >= col)
          continue; //미로의 range를 벗어날 경우 제외
        if (
          !(
            fireArr[coord[0]][coord[1]] === "." ||
            fireArr[coord[0]][coord[1]] === "J"
          )
        )
          continue; //.이나 J는 덮어씌울 수 있지만, #는 탐색하면 안되므로 제외
        fireArr[coord[0]][coord[1]] = fireArr[cur[0]][cur[1]] + 1;
        //이전 좌표의 값 (이전 좌표까지 불꽃이 퍼지는데 걸린 시간) 에서 1 더한 값을 현재 좌표에 저장
        //불이 퍼지는 시간을 모든 좌표에 대해 구하기 위함
        queue.enQueue([coord[0], coord[1]]); //상하좌우 좌표 큐에 enQueue
      }
    }
  }
  return jihoon; //지훈이 시작점만 리턴
  //배열은 주소값을 그대로 함수에 넘기기 때문에 함수 내에서 변경한 값이 저장된다
};

불 경로 저장용 배열 (fireArr) 에 불이 퍼지는데 걸리는 시간을 모든 좌표에 대하여 구하기 위해 함수를 만들었다

이 배열은 후에 지훈이가 불보다 먼저 특정 좌표에 도달할 수 있는지 여부를 검사하는 데에 사용된다

1. 지훈이 움직이기

const jihoonMove = (fireArr, jihoonArr, row, col, jihoonPos) => {
  let queue = new Queue(); //새로운 큐 선언
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ]; //상하좌우 가중치
  queue.enQueue(jihoonPos); //큐에 지훈이의 시작좌표 enQueue
  jihoonArr[jihoonPos[0]][jihoonPos[1]] = 1; //시작좌표는 1로 시작
  //마지막 탈출할때 맨 끝 칸에서 1만큼 더 가야 탈출이므로 시작점에서부터 먼저 더해줌
  while (!queue.ifEmpty()) { //큐가 빌 때까지 탐색
    let cur = queue.deQueue(); //큐에 있는 좌표 deQueue
    for (let i = 0; i < 4; i++) { //deQueue한 좌표의 상하좌우 좌표 탐색
      let coord = [cur[0] + dir[0][i], cur[1] + dir[1][i]]; //가중치 더해서 새로운 좌표 만들기
      if (coord[0] < 0 || coord[0] >= row || coord[1] < 0 || coord[1] >= col) {
        console.log(jihoonArr[cur[0]][cur[1]]);
        return;
        //만약 좌표가 바운더리를 벗어났을 경우 지훈이가 탈출한 것이므로
        //직전 좌표의 값 (탈출하는데 걸린 시간) 을 출력하고 함수를 종료한다
        //시작점이 1로 시작했으므로 출력할 땐 1 더할 필요 없이 바로 출력해도 된다
      }
      if (!(jihoonArr[coord[0]][coord[1]] === ".")) continue;
      //새로운 좌표가 .이 아닐 경우 (# 또는 F) 해당 경로로 움직일 수 없으므로 제외
      if (jihoonArr[cur[0]][cur[1]] + 1 > fireArr[coord[0]][coord[1]]) continue;
      //지훈이가 해당 좌표까지 움직이는데 걸리는 시간이 불이 퍼지는데 걸리는 시간보다 느릴 경우
      //이미 불이 퍼져 해당 경로로 지나갈 수 없으므로 제외
      //불이 퍼지는데 걸리는 시간은 fireArr에 저장되어 있으므로 이를 참고한다
      jihoonArr[coord[0]][coord[1]] = jihoonArr[cur[0]][cur[1]] + 1;
      //현재 좌표까지 도달하는데 걸린 시간은 직전 좌표까지 걸린 시간 + 1 저장
      queue.enQueue([coord[0], coord[1]]);
      //현재 좌표 큐에 저장 (상하좌우 탐색 위함)
    }
  }
  console.log("IMPOSSIBLE");
  //반복문 중간에 탈출하지 못했다면 미로 전체를 탐색해도 빠져나갈 경로가 없다는 뜻이므로
  //지훈이는 탈출할 수 없다
  //따라서 IMPOSSIBLE 출력하고 함수 종료
};

가장 먼저 탈출구를 발견하자마자 걸린 시간을 출력하고 함수를 종료한다

반복문이 끝날 때까지 탈출구를 못 찾았을 경우 탈출할 수 없는 것으로 간주한다

한 함수 내에서 반복문을 여러 개 돌리면 헷갈리므로 함수로 분리하여 동작시켰다