[JavaScript/BFS] 백준 골드 4 : 4179 - 불!

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

4179번: 불!

---

📌 작성한 코드 

// 4179
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [R, C] = input.shift().split(" ").map(Number);
const map = input.map((row) => row.split(""));

let [jx, jy] = [0, 0];
const fires = [];

for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
        if (map[i][j] === "J") {
            jx = i;
            jy = j;
        }
        if (map[i][j] === "F") {
            fires.push([i, j, 0]);
        }
    }
}

const fireVisited = Array.from({ length: R }, () => new Array(C).fill(Infinity));
const personVisited = Array.from({ length: R }, () => new Array(C).fill(false));

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

const fire = () => {
    const queue = [...fires];
    fires.forEach(([x, y, t]) => {
        fireVisited[x][y] = t;
    });

    let idx = 0;
    while (queue.length > idx) {
        const [x, y, t] = queue[idx++];

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= R || ny < 0 || ny >= C || map[nx][ny] !== ".") continue;
            if (fireVisited[nx][ny] === Infinity) {
                queue.push([nx, ny, t + 1]);
                fireVisited[nx][ny] = t + 1;
            }
        }
    }
};

const move = (a, b) => {
    const queue = [];
    queue.push([a, b, 0]);

    let idx = 0;
    while (queue.length > idx) {
        const [x, y, t] = queue[idx++];

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= R || ny < 0 || ny >= C) return t + 1;
            if (map[nx][ny] !== ".") continue;
            if (t + 1 < fireVisited[nx][ny] && !personVisited[nx][ny]) {
                queue.push([nx, ny, t + 1]);
                personVisited[nx][ny] = t + 1;
            }
        }
    }

    return -1;
};

fire();
const answer = move(jx, jy);
answer === -1 ? console.log("IMPOSSIBLE") : console.log(answer);

 

📌 풀이

1. 불을 bfs를 통해 확산시킨다 -> 해당 `fireVisited` 배열에는 불이 몇분에 해당 위치에 도달하는지 저장한다.

2. 지훈이를 bfs를 통해 이동시킨다 -> 해당 위치가 불이 번지기 전이고(해당 위치까지 도달하는데 걸린 시간이 불이 번진 시간 보다 작아야함), 이전에 도달한 적이 없다면 해당 위치로 이동한다. -> 이동할 수 있는 칸이 있는 동안 계속 해서 반복한다. 

 

✅ 성공