[JavaScript/DFS] 백준 골드 4 : 2573번 - 빙산

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

2573번: 빙산

---

📌 작성한 코드

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

const [N, M] = input.shift().split(" ").map(Number);
let iceberg = input.map((i) => i.split(" ").map(Number));

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

const meltIce = (temp) => {
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (iceberg[i][j] > 0) {
                let count = 0;
                for (let k = 0; k < 4; k++) {
                    const nx = i + dx[k];
                    const ny = j + dy[k];

                    if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                        if (iceberg[nx][ny] === 0) {
                            count++;
                        }
                    }
                }
                if (temp[i][j] < count) temp[i][j] = 0;
                else temp[i][j] -= count;
            }
        }
    }
    return temp;
};

const dfs = (x, y, temp, visited) => {
    const stack = [];
    stack.push([x, y]);
    visited[x][y] = true;

    while (stack.length) {
        const [a, b] = stack.pop();
        for (let i = 0; i < 4; i++) {
            const nx = a + dx[i];
            const ny = b + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (temp[nx][ny] > 0 && !visited[nx][ny]) {
                    stack.push([nx, ny]);
                    visited[nx][ny] = true;
                }
            }
        }
    }
};

const countIceberg = (temp) => {
    let ice = 0;
    const visited = Array.from(new Array(N), () => new Array(M).fill(false));
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (temp[i][j] > 0 && !visited[i][j]) {
                dfs(i, j, temp, visited);
                ice++;
            }
        }
    }
    return ice;
};

const solution = () => {
    if (countIceberg(iceberg) >= 2) return 0;
    let answer = 1;
    while (true) {
        const tempArr = iceberg.map((v) => [...v]);
        const changed = meltIce(tempArr);
        const count = countIceberg(changed);

        if (count >= 2) return answer;
        if (count === 0) return 0;
        iceberg = changed.map((v) => [...v]);
        answer++;
    }
};

console.log(solution());

 

📌 풀이 

✅ 1. 빙산 녹이기 

- 바다(0)와 맞닿아있는 부분의 개수만큼 빙산을 녹이는 함수 

- 반복문을 돌면서 해당 위치에 빙하가 있다면 상하좌우를 확인해서 바다와 맞닿은만큼 녹여준다.

 

- 주의! 

-> 원본 iceberg를 바로 녹이고 다른 부분의 빙하를 녹이게 되면, 앞서 녹인 빙하 때문에 다른 부분의 빙하를 녹이는 과정에서 바다와 맞닿아있는 부분의 수가 증가될 수 있음

-> 그래서 맞닿아있는 부분의 수는 원본인 iceberg를 보고 확인하고, 실제 녹이는 것은 입력으로 들어온 temp 배열을 녹인다 

- 빙하는 0보다 더 녹을 수 없기 때문에 맞닿은 바다의 수가 현재 빙하의 높이보다 크다면 0으로 설정해주고, 아니면 수만큼 빙하를 녹인다.

const meltIce = (temp) => {
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (iceberg[i][j] > 0) {
                let count = 0;
                for (let k = 0; k < 4; k++) {
                    const nx = i + dx[k];
                    const ny = j + dy[k];

                    if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                        if (iceberg[nx][ny] === 0) {
                            count++;
                        }
                    }
                }
                if (temp[i][j] < count) temp[i][j] = 0;
                else temp[i][j] -= count;
            }
        }
    }
    return temp;
};

 

✅ 2. dfs 사용해서 빙산 구하기 

- 각 빙하가 이어져있는 빙산 한개를 구하는 함수 

- 상하좌우를 확인해서 범위 내에 있고, 방문한 적이 없으면 stack에 넣고 방문하는 방식으로 빙산 한개의 범위를 다 확인한다.

const dfs = (x, y, temp, visited) => {
    const stack = [];
    stack.push([x, y]);
    visited[x][y] = true;

    while (stack.length) {
        const [a, b] = stack.pop();
        for (let i = 0; i < 4; i++) {
            const nx = a + dx[i];
            const ny = b + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (temp[nx][ny] > 0 && !visited[nx][ny]) {
                    stack.push([nx, ny]);
                    visited[nx][ny] = true;
                }
            }
        }
    }
};

 

✅ 3. 빙산의 수를 구하기

- 반복문을 돌면서 빙산을 구하는 함수

- 각 위치에 방문한 적이 없고(다른 빙산에 카운트 된 곳이 아니고), 0보다 크면(바다가 아니면) 해당 위치에서 dfs로 빙산을 구한다.

- dfs가 한번 끝나면 연결된 빙산 하나를 구한 것이므로 ice의 카운트를 세서 빙산의 개수를 세준다.

const countIceberg = (temp) => {
    let ice = 0;
    const visited = Array.from(new Array(N), () => new Array(M).fill(false));
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (temp[i][j] > 0 && !visited[i][j]) {
                dfs(i, j, temp, visited);
                ice++;
            }
        }
    }
    return ice;
};

 

✅ 4. 몇년이 지났는지 확인하기 

- 처음부터 빙산이 2개 이상으로 나뉘어져 있다면, 0을 반환(0년이 걸렸으니까) 

- iceberg를 바로 녹여버리면 다른 빙하에 맞닿는 빙하의 수에 영향이 갈 수 있으니까 복사해서 사용한다.

- 복사한 빙하 배열을 meltIce()로 녹여준다.

- 녹이고 난 다음의 빙하 배열을 countIceberg()로 빙산의 개수를 세준다 

-> 해당 빙산이 2개 이상이면 현재 년수(answer)를 출력해준다.

-> 빙하가 모두 녹아버려서 빙산이 0개라면 0을 반환해준다.(두개로 나뉘지 않음)

-> 그리고 원본 배열을 녹은 빙하 배열로 업데이트 해서 다음 반복때는 녹은 빙하 배열을 사용할 수 있게 한다.

const solution = () => {
    if (countIceberg(iceberg) >= 2) return 0;
    let answer = 1;
    while (true) {
        const tempArr = iceberg.map((v) => [...v]);
        const changed = meltIce(tempArr);
        const count = countIceberg(changed);

        if (count >= 2) return answer;
        if (count === 0) return 0;
        iceberg = changed.map((v) => [...v]);
        answer++;
    }
};

 

---

 

❗️ 주의 

- 처음부터 빙산이 2개 이상인 경우 0을 출력하는 부분 써주기 

if (countIceberg(iceberg) >= 2) return 0;

 

- 모든 빙하가 녹을 때까지 반복문 돌리기 

-> 바다와 전혀 맞닿지 않은 빙하가 있다면 반복문을 많이 돌려야 녹는 경우가 있으므로, for문과 같이 제한을 두고 반복문을 돌리지말고 while을 사용해서 모든 빙하가 녹을 때까지 반복해주고, 0을 반환해준다.

while (true) {
    // ...
    if (count === 0) return 0;
    // ...
}

 

- 복사해서 빙하 녹이기 

-> 원본 배열을 녹이면 같은 라운드에 다른 빙하를 녹이는데 영향을 미침 

-> 다 사용하고 다시 업데이트 해주기 

const tempArr = iceberg.map((v) => [...v]);
const changed = meltIce(tempArr);
const count = countIceberg(changed);
iceberg = changed.map((v) => [...v]);

 

---

 

📌 사담 

- 주의사항에 쓴 부분때문에 생각보다 오래걸렸던 문제

- 한 단계마다 디버깅 하는 습관을 까먹지 않게 주의하자!

- 이제 dfs/bfs 문제가 좀 재밌다. 풀면서 재밌었다.

 

---