[node.js] 빙산 ( 백준 2573번 )

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const graph = [];
let N, M;
rl.on("line", (line) => {
    if (!N) {
        [N, M] = line.split(" ").map(Number);
    } else {
        const row = line.split(" ").map(Number);
        graph.push(row);

        if (graph.length === N) {
            rl.close();
        }
    }
}).on("close", () => {
    const visited = [];
    for (let i = 0; i < N; i++) {
        visited[i] = new Array(M).fill(false);
    }
    const xMove = [0, 0, -1, 1];
    const yMove = [1, -1, 0, 0];

    const bfs = (y, x) => {
        const queue = [];
        queue.push({ y, x });
        visited[y][x] = 1;

        for (let i = 0; i < 4; i++) {
            const nextY = y + yMove[i];
            const nextX = x + xMove[i];
            if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
                if (graph[nextY][nextX] === 0) {
                    visited[y][x]++;
                }
            }
        }

        while (queue.length) {
            const cur = queue.shift();

            for (let i = 0; i < 4; i++) {
                const nextY = cur.y + yMove[i];
                const nextX = cur.x + xMove[i];

                if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
                    if (!visited[nextY][nextX] && graph[nextY][nextX]) {
                        visited[nextY][nextX] = 1;

                        for (let j = 0; j < 4; j++) {
                            const aroundY = nextY + yMove[j];
                            const aroundX = nextX + xMove[j];
                            if (
                                0 <= aroundY &&
                                aroundY < N &&
                                0 <= aroundX &&
                                aroundX < M
                            ) {
                                if (graph[aroundY][aroundX] === 0) {
                                    visited[nextY][nextX]++;
                                }
                            }
                        }
                        queue.push({ y: nextY, x: nextX });
                    }
                }
            }
        }
    };

    let island = 1;
    let year = 0;
    while (island < 2 && island) {
        year++;
        island = 0;
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (!visited[i][j] && graph[i][j]) {
                    island++;
                    bfs(i, j);
                }
            }
        }

        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (visited[i][j]) {
                    graph[i][j] -= visited[i][j] - 1;
                    if (graph[i][j] < 0) {
                        graph[i][j] = 0;
                    }
                }
            }
        }

        for (let i = 0; i < N; i++) {
            visited[i] = new Array(M).fill(0);
        }
    }

    if (island < 2) console.log(0);
    else {
        console.log(year - 1);
    }
});

중요한 포인트가 몇 가지 있다.
첫째는 바닷물에 접한 면적에 따라서 줄어드는 높이가 다르다는 점이다.
예컨대 3면이 바다와 접했다면 다음 차례에 3이 줄어 있어야 한다.
따라서 나는 검사할 때마다 그 점의 동서남북을 모두 체크하여 0인 부분을 세주었다.

두번째는 줄어들 때, 한 꺼번에 줄여야 한다는 점이다.
가령 ㄱ자 모양의 섬이 있다고 해보자.
이 때, 좌측 위 다음 우측 위, 그 다음 마지막으로 우측 아래를 방문한다고 할 때, 우측 위가 사라지면 어떻게 될까?
우측 아래는 자신의 바로 위가 섬이었다는 사실을 모를 테니 바다가 한 면 더 접해진 것으로 생각될 수 있다.
그렇기 때문에 접한 면을 세놓았다가 모든 정점에 대해 방문이 끝나면 한꺼번에 줄여주어야 한다.
따라서 나는 첫 방문 시에는 visisted를 1로 설정하였다.
1인 이유는, 아예 방문안한 것과, 방문했지만 줄지는 않은 것, 그 다음부터 줄어들 것으로 가정했다.
당연히 visited의 최댓값은 5가 된다.

세번째는 while문의 탈출 조건인데, 여기서도 두 개다.
두 조건을 나눠서 설명해보자면,
세번째는 섬이 2개 이상이 되면 탈출해야 한다는 점이다.
내가 작성한 코드에서는 방문을 체크해뒀다가 섬을 나중에 녹이는(?) 것이기 때문에, 실제 녹은 시점과 계산 시점이 다를 수 있다.
while문이 다음 차례에 섬이 2개인 것을 판단할 수 있기 때문이다.
따라서 -1을 마지막에 해주었다.

네번째는 while문의 탈출 조건 2번째인데 빙산이 2개 이상으로 분화되기 전에 다 녹아버린 경우이다.
따라서 island가 있다는 전제를 넣어주었다.

dfs든 bfs든 그렇게 어려운 문제는 아닌데, 제약 조건들에서 시간을 많이 먹혔다.
코드에 중복이 많은 부분도 조금 아쉽다.