백준 4179 불!

링크 : https://www.acmicpc.net/problem/4179

문제 설명

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

---

문제 풀이

• 1. input 처리
  • jIndex : 지훈의 좌표
  • fireIndex : 불의 좌표
• 2. bfs 로직 구현
  • 지훈의 좌표를 통해 지훈이 갈 수 있는 위치를 jIndex에 추가 및 arr 초기화
    •   지훈의 좌표가 arr상에 'J'가 아닐 경우(불에의해 'F'로 될 수 있음) 검사 안함
    •   이 때, 탈출을 할 수 있는 좌표면 answer를 count + 1로 초기화
  • answer가 0이 아니면 break -> 탈출한 것이므로 더이상 검사할 필요가 없음
  • 불의 좌표를 통해 불이 갈 수 있는 위치를 fireIndex에 추가 및 arr 초기화
• 3. 최종 결과
  • answer가 0이면 'IMPOSSIBLE' 리턴, 아니면 answer 값 리턴

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

const [r, c] = inputs[0].split(" ").map(Number);
let arr = [];

let jIndex = [];
let fireIndex = [];
for (let i = 1; i <= r; i++) {
  const input = inputs[i].split("");
  arr.push(input);
  input.forEach((value, xIndex) => {
    if (value === "J") jIndex.push([i - 1, xIndex, 0]);
    else if (value === "F") fireIndex.push([i - 1, xIndex]);
  });
}

let move = [
  [-1, 0],
  [1, 0],
  [0, 1],
  [0, -1],
];

let answer = 0;
const bfs = () => {
  while (jIndex.length > 0) {
    // 지훈의 이동
    let jLen = jIndex.length;
    for (let i = 0; i < jLen; i++) {
      let [jy, jx, count] = jIndex.shift();
      // 지훈이 살아있다면 (불에 타죽었으면 해당 값은 'F'로 변함)
      if (arr[jy][jx] !== "J") continue;

      move.forEach((j) => {
        let my = jy + j[0];
        let mx = jx + j[1];
        if (my >= 0 && my < r && mx >= 0 && mx < c && arr[my][mx] === ".") {
          jIndex.push([my, mx, count + 1]);
          arr[my][mx] = "J";
        } else if (my >= r || my < 0 || mx < 0 || mx >= c) {
          // 탈출
          answer = count + 1;
          return;
        }
      });
    }

    if (answer !== 0) break;

    // 불의 이동
    let fireLen = fireIndex.length;
    for (let i = 0; i < fireLen; i++) {
      let [fy, fx] = fireIndex.shift();
      move.forEach((m) => {
        let my = fy + m[0];
        let mx = fx + m[1];
        if (
          my >= 0 &&
          my < r &&
          mx >= 0 &&
          mx < c &&
          arr[my][mx] !== "#" &&
          arr[my][mx] !== "F"
        ) {
          arr[my][mx] = "F";
          fireIndex.push([my, mx]);
        }
      });
    }
  }
};

bfs();

console.log(answer === 0 ? "IMPOSSIBLE" : answer);

 

---

결론

핵심은 해당 좌표에서 갈 수 있는 경우를 적절히 판단하여 최종 결과를 구하는 문제 -> 안하면 시간초과 날 것 같음

ex. 위의 로직상 불이 이동했을 때 지훈의 좌표가 arr[]상 'J' -> 'F'로 초기화 되었을 때, 더 이상 해당 좌표에서 지훈은 움직일 수 없음