[백준2573_자바스크립트(javascript)] - 빙산

🔴 문제

빙산

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [nm, ...map] = fs
  .readFileSync(path, 'utf-8')
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, m] = nm;

const getIce = () => {
  const ice = [];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (map[i][j] > 0) ice.push([i, j]);
    }
  }

  return ice;
};

const meltIce = (Ice) => {
  const dx = [1, -1, 0, 0];
  const dy = [0, 0, 1, -1];
  const meltingIce = [];

  for (const [x, y] of Ice) {
    let meltingCnt = 0;

    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 (map[nx][ny] === 0) meltingCnt++;
    }

    meltingIce.push([x, y, meltingCnt]);
  }

  for (const ice of meltingIce) {
    const [x, y, size] = ice;
    map[x][y] -= size;

    if (map[x][y] < 0) map[x][y] = 0;
  }
};

const dfs = (x, y, visited) => {
  if (x < 0 || y < 0 || x >= n || y >= m) return;
  if (visited[x][y] <= 0) return;

  visited[x][y] = -1;

  dfs(x + 1, y, visited);
  dfs(x - 1, y, visited);
  dfs(x, y + 1, visited);
  dfs(x, y - 1, visited);
};

let year = 0;
while (true) {
  const ice = getIce();

  meltIce(ice);

  let iceCnt = 0;
  const visited = map.map((it) => it.slice());
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (visited[i][j] > 0) {
        dfs(i, j, visited);

        iceCnt += 1;
      }
    }
  }

  year += 1;
  if (iceCnt === 0) {
    console.log(0);
    break;
  } else if (iceCnt > 1) {
    console.log(year);
    break;
  }
}

🟢 풀이

⏰ 소요한 시간 : -

구현할 내용이 많아서 그렇지 차곡차곡 하면 쉬운 문제
구현 방향은 아래와 같다.

1. 맵을 전체 순회하면서 0 이상의 값이 있나 확인. 즉 얼음의 위치 확인
   만약, 0 이상의 값이 있으면 빙산이 녹을 수 있으므로 해당 위치를 큐에 넣음
2. 얼음이 있다면 해당 위치로 상하좌우 탐색해서 해당 정보를 배열에 추가
3. 2번의 과정이 끝났다면, 녹아야 할 얼음 정보를 순회하면서 기존 map에 반영
4. dfs를 수행하며 얼음이 몇 덩이인지 확인
5. dfs의 수행결과가 얼음이 녹을 수 없는 상태인 0이거나 2덩이 이상으로 갈라진 2 이상이라면 반복 종료

먼저 1번 과정을 수행하기 위해 getIce라는 함수를 만들었다. map을 순회하면서 0보다 큰 값을 담아 리턴한다.
2번 3번 과정은 metlIce함수에서 진행했다. 1번에서 만들어진 얼음들을 순회하며 상하좌우 돌아준다.
만약 상하좌우가 0이라면 meltingCnt를 증가시켜준다. 하나의 얼음을 순회하고 나서 해당 좌표와 meltingCnt를 meltingIce배열에 넣어준다. 맵에 바로 적용하면 다음 탐색에 영향을 주기 때문이다.
모든 얼음 순회가 끝나면 meltingIce배열을 순회하며 실제 map에 적용한다.
4번 과정은 dfs함수에서 진행했다. 일반적인 dfs로 방문을 체크해주기 위해 map을 복사해서 visited 배열을 만들어 dfs의 매개변수로 같이 전달해주었다. 한 번의 dfs가 끝나면 iceCnt를 증가시켜 덩어리수를 세어준다.
위의 모든 코드를 호출하는 곳은 while문 내부인데 한 번의 반복이 1년 로직이다. 따라서 1년이 지난 후 iceCnt로 종료 조건을 탐색하여 종료한다.

🔵 Ref