백준 2638: 치즈 - javascript(bfs)

문제 출처 

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

 

정답 풀이 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m] = input.shift().split(' ').map(v => +v);
const arr = [];
for (let i = 0; i < n; i++) {
    arr.push(input[i].split(' ').map(v => +v));
}

function solution(n, m, graph) {
    let answer = 0;
    bfs(n, m, graph); // 초기 외부 공기(-1)로 표시

    while (true) {
        let hasCheese = false; // 치즈가 남아있는지 확인
        let melting = []; // 이번 턴에 녹을 치즈의 좌표를 저장

        // 모든 좌표를 순회하며 치즈가 있는지 확인
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                if (graph[i][j] === 1) { 
                    hasCheese = true; // 치즈가 있음을 표시
                    if (isMelting(i, j, graph)) { // 치즈가 녹을 수 있는지 확인
                        melting.push([i, j]); // 녹을 치즈의 좌표를 저장
                    }
                }
            }
        }

        if (!hasCheese) break; // 치즈가 더 이상 없으면 종료

        // 녹을 치즈를 공기로 변환(-1)
        for (let [x, y] of melting) {
            graph[x][y] = -1;
        }

        // 녹은 치즈 주변을 다시 외부 공기로 업데이트
        updateOuterAir(n, m, graph, melting);

        answer++; // 한 턴 경과
    }

    return answer; // 모든 치즈가 녹는 데 걸린 시간(턴 수)을 반환

    // 주어진 좌표의 치즈가 녹을 수 있는지 확인하는 함수
    function isMelting(x, y, graph) {
        const dx = [-1, 1, 0, 0];
        const dy = [0, 0, -1, 1];
        let cnt = 0;

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

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 범위를 벗어나는 경우
            if (graph[nx][ny] === -1) cnt++; // 주변에 외부 공기가 있는지 확인
        }

        return cnt >= 2; // 외부 공기와 2면 이상 접촉한 치즈만 녹음
    }

    // 녹은 치즈 주변을 외부 공기로 업데이트하는 함수
    function updateOuterAir(n, m, graph, melting) {
        const dx = [-1, 1, 0, 0];
        const dy = [0, 0, -1, 1];

        const queue = [...melting]; // 녹은 치즈의 좌표를 큐에 저장

        while (queue.length) {
            const [curX, curY] = queue.shift();
            for (let i = 0; i < 4; i++) {
                let nx = curX + dx[i];
                let ny = curY + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 범위를 벗어나는 경우
                if (graph[nx][ny] !== 0) continue; // 이미 외부 공기가 아니거나 치즈가 없는 경우
                graph[nx][ny] = -1; // 외부 공기로 업데이트
                queue.push([nx, ny]); // 새로 외부 공기가 된 좌표를 큐에 추가
            }
        }
    }

    // 초기 외부 공기를 -1로 표시하는 BFS 함수
    function bfs(n, m, graph) {
        const dx = [-1, 1, 0, 0];
        const dy = [0, 0, -1, 1];

        const queue = [[0, 0]]; // (0, 0)에서 시작하여 외부 공기를 찾음
        graph[0][0] = -1; // 시작 지점을 외부 공기로 설정

        while (queue.length) {
            const [curX, curY] = queue.shift();
            for (let i = 0; i < 4; i++) {
                let nx = curX + dx[i];
                let ny = curY + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 범위를 벗어나는 경우
                if (graph[nx][ny] !== 0) continue; // 이미 외부 공기이거나 치즈가 아닌 경우
                graph[nx][ny] = -1; // 외부 공기로 표시
                queue.push([nx, ny]); // 큐에 추가하여 연쇄적으로 외부 공기를 찾음
            }
        }
    }
}

console.log(solution(n, m, arr));