[백준 2573 - Node.js] 빙산

🔗 문제 링크

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

2573번: 빙산

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input.shift().split(' ').map(Number);
const iceberg = input.map(v => v.split(' ').map(Number));
const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];

const melt = () => {
  iceberg.forEach((row, x) => {
    row.forEach((height, y) => {
      if (height > 0) {
        let count = 0;
        for (let i = 0; i < 4; i++) {
          const nx = x + offset[i][0];
          const ny = y + offset[i][1];
          if (iceberg[nx][ny] === 0) {
            count++;
          }
        }
        iceberg[x][y] -= count;
        if (iceberg[x][y] <= 0) {
          iceberg[x][y] = -1;
        }
      }
    });
  });
};

const dfs = (start, visited) => {
  const stack = [start];
  while (stack.length) {
    const [x, y] = stack.pop();
    for (let i = 0; i < 4; i++) {
      const nx = x + offset[i][0];
      const ny = y + offset[i][1];
      if (nx === 2 && ny === 5) {
      }
      if (!visited[nx][ny] && iceberg[nx][ny] > 0) {
        visited[nx][ny] = true;
        stack.push([nx, ny]);
      }
    }
  }
}

const changeMinusToZero = () => {
  iceberg.forEach((row, x) => {
    row.forEach((height, y) => {
      if (height === -1) {
        iceberg[x][y] = 0;
      }
    });
  });
};

let year = 0;

while (true) {
  const visited = [...Array(N)].map(() => Array(M).fill(false));
  let count = 0;
  for (let i = 1; i < N - 1; i++) {
    for (let j = 1; j < M - 1; j++) {
      if (!visited[i][j] && iceberg[i][j] > 0) {
        visited[i][j] = true;
        dfs([i, j], visited);
        count++;
      }
    }
  }
  if (count >= 2) {
    console.log(year);
    break;
  } else if (count === 0) {
    console.log(0);
    break;
  }
  melt();
  changeMinusToZero();
  year++;
}

 

빙산을 DFS로 방문하면서 연결 요소(Connected Component)의 개수를 센다. 연결 요소의 개수가 2 이상이라면 현재 시점에서 빙산이 최초로 분리된 것이므로 현재까지 경과된 연도수(year)를 반환한다. 만약 연결 요소가 없다면 빙산이 모두 녹은 시점이므로 0을 반환한다.

 

만약 연결 요소의 개수가 1이라면 아직 빙산이 분리되지 않았으므로 계속 반복문을 진행한다.

melt 함수에서는 문제의 조건에 따라 바다에 접한 면의 개수만큼 빙산의 높이를 줄인다.

여기서 주의할 점은 빙산을 녹일 때, xy 좌표 순서대로 녹이게 되는데(forEach) 하나씩 녹이면서 중간에 다 녹은 빙산 때문에 다음에 녹여야할 빙산의 바다에 접한 면의 개수가 달라질 수도 있다. 그래서 빙산을 하나씩 녹이면서 만약 다 녹았다면(높이가 0이하라면) 높이를 -1로 변경하였다. 이렇게 하면 중간에 다 녹아버린 빙산은 -1이 되고, 처음부터 바다였던 칸은 0이므로 바다에 접한 면의 개수를 셀 때 앞에서 먼저 녹은 빙산의 영향을 받지 않고 0의 개수로 셀 수 있게 된다.

 

다음 반복문에서도 바다에 접한 면의 개수를 셀 때 0의 개수로 셀 것이므로, melt 함수가 끝난 후에는 changeMinusToZero 함수에서 -1을 다시 모두 0으로 변경해주었다.

 

melt와 changeMinusToZero를 실행한 후에 연도수(year)를 증가시킨다.

 

이 과정을 반복하다가 최초로 빙산이 분리되거나, 모든 빙산이 다 녹아서 방문할 수 없을 때 반복문을 빠져나가게 된다.

 

⛔ 반례 모음

5 7
0 0 0 0 0 0 0
0 3 3 2 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0
출력: 0

5 7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 10 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
출력: 0

5 7
0 0 0 0 0 0 0
0 3 3 1 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0
출력: 1

5 7
0 0 0 0 0 0 0
0 3 6 3 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
출력: 2

5 7
0 0 0 0 0 0 0
0 3 6 0 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
출력: 0

5 7
0 0 0 0 0 0 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0
출력: 0

5 7
0 0 0 0 0 0 0
0 9 8 3 8 9 0
0 9 8 0 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0
출력: 5

5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
출력: 0

7 7
0 0 0 0 0 0 0
0 1 1 0 1 1 0
0 1 9 1 9 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0
출력: 2