[BOJ / Node.js] 2638. 치즈

2638번: 치즈

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

예제 입력 1 복사

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

예제 출력 1 복사

4

 

Solve

• 문제풀이를 위해 먼저 순서를 정리했습니다.

1. 내부공기와 외부공기를 분류합니다. => 모든 종이의 가장자리에는 치즈가 없으므로 가장자리 기준으로 검사. 외부공기는 -1이라고 가정합니다.(BFS를 활용)
2. 외부공기와 2면 이상 접촉한 치즈는 녹습니다 => 녹을 예정인 치즈는 2로 변환합니다. (BFS 활용)
3. 녹을 예정일 치즈(2)를 한번에 제거합니다. => 치즈가 모는종이에 없다면 반복문을 종료합니다.
4. 1번으로 돌아갑니다.

• 주어진 배열에서 치즈의 개수를 먼저 센 후 cheese변수에 할당하였습니다. 치즈가 녹을 때마다 cheese값을 빼주면서, 모눈종이에 치즈가 남아있는지의 여부를 계산하였습니다.

Code

// 큐
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    empty() {
        return this.length === 0 ? 1 : 0;
    }

    enqueue(element) {
        const newNode = new Node(element);
        if (!this.head) this.head = newNode;
        else this.tail.next = newNode;

        this.tail = newNode;
        this.length++;
    }

    dequeue() {
        if (!this.head) return -1;
        const data = this.head.data;
        this.head = this.head.next;
        this.length--;
        return data;
    }

    getSize() {
        return this.length;
    }

    front() {
        if (!this.length) return -1;
        return this.head.data;
    }

    back() {
        if (!this.length) return -1;
        return this.tail.data;
    }
}

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

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const [n,m] = input.shift().split(' ').map(el=>+el);
const matrix = input.map(el=>el.split(' ').map(el=>+el));
let save = null;
let visited = null;
let answer = 0;
let cheese = 0;
for(let i = 0; i < n; i++) {
    for(let j = 0; j < m; j++) {
        if(matrix[i][j] === 1) cheese++;
    }
}

const divideAir = (matrix) => {
    matrix[0][0] = -1;
    const queue = new Queue();
    queue.enqueue([0,0]);

    while(!queue.empty()) {

        const [x, y] = queue.dequeue();
        for(let i = 0; i < 4; i++) {
            const nx = x + dx[i]; const ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(matrix[nx][ny] !== 0) continue;

            matrix[nx][ny] = -1;
            queue.enqueue([nx, ny]);
        }
    }
}

const initAir = (matrix) => {
    for(let i = 0 ; i < n; i++) {
        for(let j = 0; j < m; j++) {
            if(matrix[i][j] === -1) matrix[i][j] = 0;
        }
    }
}
const isMelt = (matrix, x, y) => {
    let count = 0;
    for(let i = 0 ; i < 4; i++) {
        const nx = x + dx[i]; const ny = y + dy[i];
        if(matrix[nx][ny] === -1) count++;
        if(count >= 2) break;
    }
    return count >= 2;
}
const convertCheese = (matrix, sx, sy) => {
    if(matrix[sx][sy] !== 1) return;
    if(visited[sx][sy]) return;
    visited[sx][sy] = true;
    const queue = new Queue();
    queue.enqueue([sx, sy]);

    while(!queue.empty()) {
        const [x, y] = queue.dequeue();

        if(isMelt(matrix, x, y)) {
            matrix[x][y] = 2;
            save.push([x, y]);
        }
        for(let i = 0 ; i < 4; i++) {
            const nx = x + dx[i]; const ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(matrix[nx][ny] !== 1) continue;
            if(visited[nx][ny]) continue;

            queue.enqueue([nx, ny]);
            visited[nx][ny] = true;
        }
    }
}



while(true) {
    answer++;
    save = [];
    initAir(matrix);
    divideAir(matrix);


    visited = Array.from({length:n},()=>Array.from({length:m},()=>false));
    for(let i = 0 ; i < n; i++) {
        for(let j = 0; j < m; j++) {
            convertCheese(matrix, i, j);
        }
    }

    for(let i = 0; i < save.length; i++) {
        const [x, y] = save[i];
        matrix[x][y] = -1;
        cheese--;
    }
    if(cheese <= 0) break;
}


console.log(answer);