[백준] 2636 치즈 (Javascript)

문제

BOJ2636_치즈

요구사항 분석

• 한 시간마다 치즈의 외곽부(공기랑 닿는 부분)가 녹는다.
• 치즈에 구멍이 뚫려있어도 외곽이랑 닿는 부분이 아니라면 공기랑 닿는 부분이 아니다.
• 치즈가 모두 녹기까지 걸리는 시간과, 모두 녹기 한 시간 전 남아있는 치즈 조각의 수를 구해야 한다.

전체 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const cheese = input.slice(1).map((e) => e.split(' ').map(Number));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
let count = 0;
let hours = 0;

while (true) {
    let cnt = countCheese();
    if (cnt === 0) break; // 치즈가 더이상 없을 경우 종료
    count = cnt;
    checkCheese();
    hours++;
}

console.log(hours + '\n' + count);

// 공기랑 닿는 부분 녹이기
function checkCheese() {
    // 빈칸 = 0, 치즈 = 1
    const visited = cheese.map((e) => [...e]);
    bfs(0, 0, visited);
}

// 치즈 개수 세기
function countCheese() {
    let cnt = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (cheese[i][j]) cnt++;
        }
    }
    return cnt;
}

function bfs(x, y, visited) {
    const queue = [[y, x]];
    visited[y][x] = 1;
    let front = 0;
    while (queue.length > front) {
        const [y, x] = queue[front++];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if (cheese[ny][nx]) cheese[ny][nx] = 0;
                if (!visited[ny][nx]) {
                    queue.push([ny, nx]);
                    visited[ny][nx] = 1;
                }
            }
        }
    }
}

접근법

공기랑 닿는 부분 녹이기

• 만약 2중 for문으로 0인 부분을 찾아서 0이랑 맞닿인 부분을 녹인다면 치즈 내부에 있는 구멍까지 녹게되기 때문에 다른 방법을 찾아야 한다.
• 치즈의 외부를 판별할 수 있다면 치즈의 외곽도 녹일 수 있을 것이다. 치즈의 외부를 판별하기 위해 [0][0]위치부터 상,하,좌,우를 확인하며 BFS를 수행한다. 문제에서 판의 테두리 부분은 치즈를 놓을 수 없다고 나와있으니 [0][0] 위치는 항상 치즈가 아니므로 해당 위치부터 BFS를 수행하며 다음 위치가 치즈(1)일 경우 1을 0으로 바꿔서 녹여주고 방문처리 해준다(visited[ny][nx] = 1;).
• 다음 위치가 치즈일 경우 0으로 바꿔주었기 때문에 다음 스텝에서 if (cheese[ny][nx]) 조건문에 걸리지 않고, 방문 처리를 해주었기 때문에 if (!visited[ny][nx]) 조건문에 걸리지 않으므로 BFS가 치즈 내부로 들어가지 않는다.

치즈 개수 세기

• 치즈가 모두 녹기 한 시간 전의 치즈 조각의 개수를 알아야 하기 때문에 치즈 개수를 세준다.
• 치즈 개수가 0개라면 치즈가 모두 녹은 것이므로 while문을 종료시키면 되고, count 변수에는 이전 반복문에서 구한 치즈의 개수가 저장되어 있기 때문에 while문이 종료되었을 때 count 변수에는 치즈가 모두 녹기 한 시간 전의 치즈의 개수가 저장돼있다.

코드 개선

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const cheese = input.slice(1).map((e) => e.split(' ').map(Number));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
let count = 0;
let hours = 0;
let cnt = countCheese();

while (true) {
    if (cnt === 0) break; // 치즈가 더이상 없을 경우 종료
    count = cnt;
    checkCheese();
    hours++;
}

console.log(hours + '\n' + count);

// 공기랑 닿는 부분 녹이기
function checkCheese() {
    // 빈칸 = 0, 치즈 = 1
    const visited = cheese.map((e) => [...e]);
    bfs(0, 0, visited);
}

// 치즈 개수 세기
function countCheese() {
    let cnt = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (cheese[i][j]) cnt++;
        }
    }
    return cnt;
}

function bfs(x, y, visited) {
    const queue = [[y, x]];
    visited[y][x] = 1;
    let front = 0;
    while (queue.length > front) {
        const [y, x] = queue[front++];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if (cheese[ny][nx]) {
                    cheese[ny][nx] = 0;
                    cnt--;
                }
                if (!visited[ny][nx]) {
                    queue.push([ny, nx]);
                    visited[ny][nx] = 1;
                }
            }
        }
    }
}

개선 내용

countCheese() 함수는 $O(N^2)$의 시간이 걸린다. 기존 코드에서는 countCheese()함수를 while문이 한 번 반복할 때마다 실행하기 때문에 $N$이 커질경우 시간이 매우 오래걸릴 것이다.

따라서 countCheese()함수는 맨 처음에 한 번만 실행시켜서 전역 변수 cnt에 저장해놓고, bfs()에서 치즈를 녹일때마다 cnt를 1씩 줄여나가도록 했다. 이렇게 하면 while문 안에서 countCheese()함수를 실행하지 않기 때문에 속도 측면에서 더 좋은 코드라고 할 수 있다.