[JavaScript/BFS] 백준 골드 4 : 3055 - 탈출

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

3055번: 탈출

---

📌 작성한 코드 

// 3055
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[0].split(" ").map(Number);
const board = [];
let sx, sy, ex, ey;
const waters = [];

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

for (let i = 1; i < input.length; i++) {
    const temp = input[i].split("");

    temp.forEach((v, j) => {
        if (v === "S") {
            sx = i - 1;
            sy = j;
        }
        if (v === "D") {
            ex = i - 1;
            ey = j;
        }
        if (v === "*") {
            waters.push([i - 1, j, 0]);
        }
    });

    board.push(temp);
}

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

const waterBfs = () => {
    const queue = [...waters];
    queue.forEach(([x, y, t]) => (waterVisited[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) continue;
            if (waterVisited[nx][ny] > t + 1 && board[nx][ny] === ".") {
                queue.push([nx, ny, t + 1]);
                waterVisited[nx][ny] = t + 1;
            }
        }
    }
};

const personBfs = () => {
    const queue = [];
    queue.push([sx, sy, 0]);
    personVisited[sx][sy] = true;

    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) continue;
            if (!personVisited[nx][ny] && board[nx][ny] === "." && waterVisited[nx][ny] > t + 1) {
                queue.push([nx, ny, t + 1]);
                personVisited[nx][ny] = true;
            }
            if (nx === ex && ny === ey) {
                return t + 1;
            }
        }
    }
    return "KAKTUS";
};

waterBfs();
const answer = personBfs();
console.log(answer);

 

📌 풀이 

백준 1600 - 불! 문제와 완전히 똑같은 문제이다. 해당 문제에서 불을 물로 바꾼 것과 같다. bfs를 각각 돌려서 물은 범람시키고 고슴도치는 이동시키면 되는 문제이다. 해당 문제의 포인트는 bfs를 두번 돌리기 + bfs 각각 구현하기이다.

https://youme016.tistory.com/333

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

 

(1) 물을 먼저 범람시켜야 하는 이유

물이 시작되는 위치는 한개로 정해진 것이 아니라 여러곳에서 동시에 범람되기 시작할 수 있다. 그러므로 bfs 한개를 돌리면서 물을 범람시키고, 고슴도치를 이동시키기란 정말 어려운 일이다. 그래서 우리는 물을 먼저 범람시켜서 해당 위치에 물이 범람하는데 걸린 시간을 기록할 것이다. bfs를 통해 물이 해당 위치에 도달하는 데 걸린 시간을 `waterVisted`배열에 저장하고 우리는 이 배열을 이용해서 고슴도치를 이동시킬 것이다.

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

const waterBfs = () => {
    const queue = [...waters]; // 물의 초기 좌표들 큐에 전부 넣기
    queue.forEach(([x, y, t]) => (waterVisited[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) continue;
            if (waterVisited[nx][ny] > t + 1 && board[nx][ny] === ".") {
                queue.push([nx, ny, t + 1]);
                waterVisited[nx][ny] = t + 1; // 방문 배열에 도달하는데 걸린 시간 저장하기
            }
        }
    }
};

 

(2) 고슴도치 이동하기 

이제 고슴도치도 bfs를 따라 이동시키면서 도착지에 가는 최단 경로를 찾을 것인데, 이때 이전에 구한 물의 범람 시간 배열을 사용할 것이다. 물이 해당 위치에 도달하기 전에 고슴도치가 그 위치로 이동할 수 있다면 해당 위치를 큐에 넣고, 고슴도치가 가기 전에 이미 물이 해당 위치에 도달했다면 해당 위치는 갈 수 없으므로 큐에 넣지 않는 것이다. 이렇게 해서 물이 도달하기 전인 위치만 찾아서 도착지점에 도달하는 최단 경로를 찾을 것이다. 

const personBfs = () => {
    const queue = [];
    queue.push([sx, sy, 0]);
    personVisited[sx][sy] = true;

    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) continue;
            if (!personVisited[nx][ny] && board[nx][ny] === "." && waterVisited[nx][ny] > t + 1) { // 물보다 도착 시간 작을때
                queue.push([nx, ny, t + 1]);
                personVisited[nx][ny] = true;
            }
            if (nx === ex && ny === ey) {
                return t + 1;
            }
        }
    }
    return "KAKTUS";
};

 

✅ 성공