[JavaScript/BFS] 백준 골드 4 : 2636 - 치즈

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

2636번: 치즈

---

📌 작성한 코드 

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

let total = 0;

const [N, M] = input.shift().split(" ").map(Number);
const board = input.map((str) => {
    const temp = str.split(" ");
    temp.forEach((val) => {
        if (val === "1") total++;
    });

    return temp;
});

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

const bfs = (a, b) => {
    const visited = Array.from({ length: N }, () => new Array(M).fill(false));

    let count = 0;
    const air = [];
    const cheese = [];
    air.push([a, b]);
    visited[a][b] = true;

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

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (!visited[nx][ny] && board[nx][ny] === "0") {
                air.push([nx, ny]);
                visited[nx][ny] = true;
            } else if (!visited[nx][ny] && board[nx][ny] === "1") {
                cheese.push([nx, ny]);
                visited[nx][ny] = true;
            }
        }
    }

    cheese.forEach(([x, y]) => {
        board[x][y] = "0";
        count++;
    });

    return count;
};

let answer = [];
let remain = total;

while (true) {
    const count = bfs(0, 0);
    if (count === 0) {
        break;
    }
    answer.push(remain - count);
    remain -= count;
}

console.log(answer.length);
console.log(answer.length === 1 ? total : answer[answer.length - 2]);

 

📌 설명 

문제 풀이 방법

1. bfs를 이용하여 공기와 맞닿은 부분을 구하고, 해당 부분을 녹인다.

2. 더 이상 녹일 치즈가 없을 때 까지 반복한다.

 

BFS 구현시 주의사항

1. 치즈를 바로 녹여버리면 공기와 맞닿는 부분이 늘어나서 제대로 된 계산이 불가능해진다. -> 기록해두었다가 한번에 녹이기

2. 치즈를 기준으로 bfs를 돌리면 가장자리를 찾기 어렵다. -> 공기를 기준으로 돌리기

 

✅ 성공