[JavaScript/BFS] 백준 골드 5 : 6593 - 상범 빌딩

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

6593번: 상범 빌딩

---

📌 작성한 코드 

// 6593
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 dx = [1, -1, 0, 0, 0, 0];
const dy = [0, 0, -1, 1, 0, 0];
const dz = [0, 0, 0, 0, 1, -1];

while (true) {
    const [L, R, C] = input.shift().split(" ").map(Number);
    if (L === 0 && R === 0 && C === 0) break;

    let start = [0, 0, 0];
    const map = [];

    for (let i = 0; i < L; i++) {
        const temp = [];
        for (let j = 0; j < R; j++) {
            const list = input.shift().split("");
            temp.push(list);

            list.forEach((n, k) => {
                if (n === "S") {
                    start = [i, j, k];
                }
            });
        }
        map.push(temp);
        input.shift();
    }

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

        let idx = 0;
        while (queue.length > idx) {
            const [z, x, y, count] = queue[idx++];
            map[z][x][y] = "1";

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

                if (nx < 0 || nx >= R || ny < 0 || ny >= C || nz < 0 || nz >= L) continue;
                if (map[nz][nx][ny] === ".") {
                    queue.push([nz, nx, ny, count + 1]);
                    map[nz][nx][ny] = "1";
                }
                if (map[nz][nx][ny] === "E") return count + 1;
            }
        }
        return -1;
    };

    const answer = bfs(start[0], start[1], start[2]);
    if (answer !== -1) {
        console.log(`Escaped in ${answer} minute(s).`);
    } else {
        console.log("Trapped!");
    }
}

 

📌 풀이 

삼차원 배열에서 bfs로 s->e까지의 최단 거리를 구해주는 문제이다. 최단거리를 구하는 문제이기 때문에 bfs를 사용하는 것이 좋다. 

 

0. 종료 조건 세팅하기 

0 0 0이 입력되면 종료되는 문제이기 때문에 입력받고 해당 값 확인해서 break 해줘야 한다. 

while (true) {
    const [L, R, C] = input.shift().split(" ").map(Number);
    if (L === 0 && R === 0 && C === 0) break;
    // ...
}

 

1. 3차원 배열에 빌딩 입력받기

s에서 bfs를 시작해야 하므로 입력받으면서 s의 위치도 확인해서 저장한다. 각 빌딩의 층이 공백으로 구분되어 있기 때문에 한 층을 다 입력받은 후에는 다음 공백을 제거하기 위해서 `input.shift()`를 진행한다.

let start = [0, 0, 0];
const map = [];

for (let i = 0; i < L; i++) {
    const temp = [];
    for (let j = 0; j < R; j++) {
        const list = input.shift().split("");
        temp.push(list);

        list.forEach((n, k) => {
            if (n === "S") {
                start = [i, j, k];
            }
        });
    }
    map.push(temp);
    input.shift();
}

2. bfs 작성하기 

3차원에서 상하좌우앞뒤로 이동하는 bfs를 작성해주면된다. count를 저장하고 증가시키면서 현재위치까지 오는데 걸린 시간을 같이 관리한다. 

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

    let idx = 0;
    while (queue.length > idx) {
        const [z, x, y, count] = queue[idx++];
        map[z][x][y] = "1";

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

            if (nx < 0 || nx >= R || ny < 0 || ny >= C || nz < 0 || nz >= L) continue;
            if (map[nz][nx][ny] === ".") {
                queue.push([nz, nx, ny, count + 1]);
                map[nz][nx][ny] = "1";
            }
            if (map[nz][nx][ny] === "E") return count + 1;
        }
    }
    return -1;
};

3. 정답 출력하기 

const answer = bfs(start[0], start[1], start[2]);
if (answer !== -1) {
    console.log(`Escaped in ${answer} minute(s).`);
} else {
    console.log("Trapped!");
}

 

✅ 정답