[JavaScript] 백준 2573 빙산 (JS)

빙산

📚 문제 설명

N * M 크기의 지도에 빙산과 바다가 있다.
빙산은 다음과 같이 녹는다고 할 때, 빙산이 두 덩이 이상으로 나뉘는 시점은 몇년 후인가?

• 1년 후
  • 빙산의 동서남북 바다의 갯수만큼 낮아진다.

단, 두덩이로 나뉘기 전에 모든 빙산이 사라지면 0을 리턴.

👨🏻‍💻 풀이 과정

solution 함수

• 두 덩이로 나뉠 때까지 반복.
  • iceMap을 확인하며 빙산 찾기.
    • 빙산을 찾으면 BFS() 실행.
    • 빙산 덩어리 갯수 1개 추가.
• 빙산이 두 덩어리 이상이면 종료.
• 빙산이 덩어리가 0이라면 종료.

BFS 함수 실행 1번이 빙산 한덩이.

BFS 함수

• nextMap 에 1년후 빙산 기록.
• 동서남북 확인.
  • nextMap 값 갱신.
• nextMap 리턴.

전체 코드

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

    const [N, M] = input.shift().split(' ').map(Number);

	// 현재 빙산 상황.
    let iceMap = input.map(v => v.split(' ').map(Number));

    const BFS = (nowX, nowY, visited) => {
      	// 초기값
        let Queue = [[nowX, nowY]];
        visited[nowX][nowY] = true;
        let idx = 0;
        let dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
      	// 1년후 빙산 상황.
        let nextMap = iceMap.map(v => [...v]);
      
        while (Queue.length > idx) {
            let [x, y] = Queue[idx];
            for (const [dx, dy] of dirs) {
                const nx = x + dx;
                const ny = y + dy;
              	// 범위 밖으로 나갈 경우
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

              	// 1년후 빙산 계산.
                if (iceMap[nx][ny] === 0 && nextMap[x][y] > 0) {
                    nextMap[x][y]--;
                }

              	// Queue에 같은 덩이의 빙산 추가.
                if (iceMap[nx][ny] > 0 && !visited[nx][ny]) {
                    Queue.push([nx, ny]);
                    visited[nx][ny] = true;
                }
            }
            idx++;
        }
        return nextMap;
    };

    const solution = () => {
        let timer = 0;
        while (true) {
            let visited = Array.from({length: N}, _ => Array(M).fill(false));
            let cnt = 0;

            for (let i = 0; i < N; i++) {
                for (let j = 0; j < M; j++) {
                    if (!visited[i][j] && iceMap[i][j] > 0) {
                      // 빙산 덩어리 갯수 증가.
                        cnt++;
                        iceMap = BFS(i, j, visited);
                    }
                }
            }
          	// 2덩어리 이상이면 종료.
            if (cnt >= 2) break;
          	// 덩어리가 없다면 0리턴.
            if (cnt === 0) {
                timer = 0;
                break;
            }
          	// 1년 지남.
            timer++;
        }
        console.log(timer);
    };
    solution();

시간 초과의 경우 빙산이 나뉘기 전에 전부 사라지는 경우를 계산하지 않아서 발생했다.
아래와 같은 경우 1년 후 두개의 덩어리 이상 나뉘는게 아니라 빙산이 사라지기 때문에 0을 리턴해야 한다.

5 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0

🧐 후기

출력 조건에 두 덩어리 이상 나뉘는 경우를 계산하는 부분을 언급했는데 그 부분을 빼놓고 구현을 했더니 시간초과가 나서 첫제출에 당황했다.
요구 사항을 꼼꼼히 살펴보자.