[백준] 2573 빙산 - javascript

📌 문제

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

📌 풀이

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

const [row, col] = input.shift().split(' ').map(Number);
const arr = input.map((i) => i.split(' ').map(Number));
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

const checkIsland = (arr) => {
  let islandCnt = 0;
  let visited = Array.from({ length: row }, () => Array.from({ length: col }, () => false));

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

    while (queue.length) {
      let [curX, curY] = queue.shift();

      for (let i = 0; i < 4; i++) {
        let [newX, newY] = [curX + dx[i], curY + dy[i]];
        if (newX >= 0 && newX < row && newY >= 0 && newY < col && arr[newX][newY] !== 0 && !visited[newX][newY]) {
          queue.push([newX, newY]);
          visited[newX][newY] = true;
        }
      }
    }
  };

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (arr[i][j] && !visited[i][j]) {
        bfs(i, j);
        islandCnt++;
      }
    }
  }
  return islandCnt >= 2 ? true : false;
};

const checkAllZero = (arr) => {
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (arr[i][j] !== 0) {
        return false;
      }
    }
  }
  return true;
};

let time = 0;
while (1) {
  let around = Array.from({ length: row }, () => Array.from({ length: col }, () => 0));
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (arr[i][j]) {
        for (let k = 0; k < 4; k++) {
          let [nx, ny] = [i + dx[k], j + dy[k]];
          if (nx >= 0 && nx < row && ny >= 0 && ny < col && arr[nx][ny] === 0) {
            around[i][j]++;
          }
        }
      }
    }
  }

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (arr[i][j]) arr[i][j] = arr[i][j] - around[i][j] > 0 ? arr[i][j] - around[i][j] : 0;
    }
  }
  time++;

  if (checkIsland(arr)) {
    console.log(time);
    break;
  }

  if (checkAllZero(arr)) {
    console.log(0);
    break;
  }
}

✔ 알고리즘 : 구현 + DFS

✔ time 변수를 설정하여 while 반복문 안에서 현재 칸에 0이 아닌 수라면 주변에서 0인 지역의 개수를 카운트해서 around 배열에 저장한다.

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (arr[i][j]) {
      for (let k = 0; k < 4; k++) {
        let [nx, ny] = [i + dx[k], j + dy[k]];
        if (nx >= 0 && nx < row && ny >= 0 && ny < col && arr[nx][ny] === 0) {
          around[i][j]++;
        }
      }
    }
  }
}

✔ arr[i][j] - around[i][j]로 주변 지역의 영향으로 줄어든 빙산의 높이를 업데이트한다. (음수는 불가능)

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (arr[i][j]) arr[i][j] = arr[i][j] - around[i][j] > 0 ? arr[i][j] - around[i][j] : 0;
  }
}

✔ 빙산의 높이를 업데이트했으므로 2개 이상의 섬으로 나뉘어지는지 체크한다.

if (checkIsland(arr)) {
  console.log(time);
  break;
}

✔ 2개 이상의 섬으로 나뉘어지는지는 checkIsland 함수를 통해 판단이 가능한데, 전형적인 bfs 탐색으로 구하였다. 0이 아닌 좌표를 만날때마다 visited가 false인 경우에 bfs 탐색을 진행하고 islandCnt를 1증가 시켜주었다. 👉 총 섬의 개수는 bfs탐색 횟수와 같다.

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (arr[i][j] && !visited[i][j]) {
      bfs(i, j);
      islandCnt++;
    }
  }
}

✔ 2개 이상으로 안나뉘어지고 모든 좌표가 0인 경우는 출력조건에 따라 0을 출력한다.

if (checkAllZero(arr)) {
  console.log(0);
  break;
}

✔ 난이도 : 백준 기준 골드 4