[백준] 2573번 - 빙산 풀이 및 코드 분석 (Java)

문제 링크

---

1. 문제 분석

📌 문제 개요
이 문제는 지구 온난화로 인해 빙산이 해마다 녹는 현상을 시뮬레이션하고, 빙산이 두 덩어리 이상으로 분리되는 최초 시점(년수) 을 구하는 문제입니다.

🎯 요구사항

• 빙산은 2차원 배열로 주어지며, 0은 바다, 1~10은 빙산의 높이를 의미합니다.
• 매년, 각 빙산 칸은 상하좌우에 접한 바다(0)의 수만큼 높이가 감소합니다.
• 빙산의 높이는 0 이하로 내려갈 수 없습니다.
• 매년 시뮬레이션을 진행하면서 빙산 덩어리의 개수를 세고, 2개 이상으로 나뉘는 첫 해를 출력해야 합니다.
• 만약 빙산이 전부 다 녹을 때까지 분리되지 않으면 0을 출력합니다.

📈 입력 크기 및 제약

• 3 ≤ N, M ≤ 300
• 빙산 칸 수 ≤ 10,000
• 시간 복잡도는 연산이 해마다 반복되므로, 연산당 O(NM) 이내여야 합니다.

---

2. 해결 방법

🔹 핵심 개념

• 시뮬레이션 + BFS 탐색을 조합한 문제입니다.
• 매 해마다 빙산을 녹이고, 빙산 덩어리의 개수(BFS로 탐색) 를 세는 방식으로 해결합니다.

🔑 해결 절차

1. 빙산 위치 저장: 빙산 좌표만 따로 리스트로 저장해서 연산 최적화
2. 매년 시뮬레이션 반복
   • 각 빙산 칸 기준으로 주변의 바다(0) 개수 세어 높이 감소
   • 높이가 0이 되면 빙산 제거
3. 빙산 덩어리 개수 세기 (BFS)
   • 연결된 빙산 칸을 한 덩어리로 간주
   • 덩어리가 2개 이상이면 해당 연도 출력
   • 빙산이 모두 사라졌으면 0 출력

---

3. 코드 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

  static int N, M; // 배열의 크기 (행, 열)
  static int[] drs = {0, 0, 1, -1}, dcs = {1, -1, 0, 0}; // 동서남북 방향벡터
  static int[][] board, cnt, visited; // 빙산 상태, 녹을 양, 방문 체크
  static List<int[]> coor = new LinkedList<>(); // 빙산 좌표 리스트

  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    board = new int[N][M];

    // 입력 처리 및 빙산 좌표 저장
    for (int r = 0; r < N; r++) {
      st = new StringTokenizer(br.readLine());
      for (int c = 0; c < M; c++) {
        board[r][c] = Integer.parseInt(st.nextToken());
        if (board[r][c] > 0)
          coor.add(new int[] {r, c}); // 빙산 위치만 따로 저장
      }
    }

    int year = 0;
    while (true) {
      cnt = new int[N][M]; // 매년 빙산 녹는 양 초기화

      // 1. 각 빙산 위치마다 인접한 바다(0)의 개수 세기
      for (int[] pos : coor) {
        int r = pos[0], c = pos[1];

        for (int d = 0; d < 4; d++) {
          int nr = r + drs[d], nc = c + dcs[d];
          if (isInRange(nr, nc) && board[nr][nc] == 0)
            cnt[r][c]++;
        }
      }

      // 2. 녹을 양만큼 줄이고, 남아 있는 빙산만 저장
      List<int[]> newCoor = new LinkedList<>();
      for (int[] pos : coor) {
        int r = pos[0], c = pos[1];

        board[r][c] -= cnt[r][c];
        if (board[r][c] < 0) board[r][c] = 0;

        if (board[r][c] > 0)
          newCoor.add(new int[] {r, c});
      }
      coor = newCoor;

      visited = new int[N][M]; // 방문 배열 초기화
      year++; // 1년 경과

      // 3. 빙산 덩어리 개수 세기
      int count = count();
      if (count > 1) // 두 덩어리 이상 분리됨
        break;
      else if (count == 0) { // 모두 녹음
        year = 0;
        break;
      }
    }

    System.out.println(year);
  }

  // BFS로 빙산 덩어리 개수 세기
  private static int count() {
    int cnt = 0;

    for (int[] pos : coor) {
      int r = pos[0], c = pos[1];

      if (board[r][c] > 0 && visited[r][c] == 0) {
        cnt++;

        if (cnt > 1) return cnt; // 2개 이상이면 바로 리턴

        bfs(r, c); // BFS로 같은 덩어리 모두 방문 처리
      }
    }

    return cnt;
  }

  // BFS 탐색 (빙산 덩어리 체크용)
  private static void bfs(int r, int c) {
    Queue<int[]> q = new LinkedList<>();
    visited[r][c] = 1;
    q.add(new int[] {r, c});

    while (!q.isEmpty()) {
      int[] cur = q.poll();
      r = cur[0];
      c = cur[1];

      for (int d = 0; d < 4; d++) {
        int nr = r + drs[d], nc = c + dcs[d];

        if (canGo(nr, nc)) {
          visited[nr][nc] = 1;
          q.add(new int[] {nr, nc});
        }
      }
    }
  }

  // 배열 범위 체크
  private static boolean isInRange(int r, int c) {
    return r >= 0 && c >= 0 && r < N && c < M;
  }

  // 방문 가능한 조건
  private static boolean canGo(int r, int c) {
    return isInRange(r, c) && visited[r][c] == 0 && board[r][c] > 0;
  }
}

---

4. 코드 분석

🔹 주요 알고리즘

• 빙산 위치 추적: coor 리스트로 빙산 좌표만 관리하여 불필요한 탐색 방지
• 사방 바다 수 카운팅: cnt[r][c] 배열을 따로 사용해 동시에 갱신 방지
• 덩어리 수 세기: BFS로 덩어리 개수 파악
• 시뮬레이션 루프: 매 해마다 빙산 상태 갱신 후 분리 여부 확인

🔹 시간 복잡도 분석

연산	시간 복잡도
바다 탐색 및 높이 감소	O(K) (K: 빙산 칸 수)
덩어리 세기 (BFS)	O(K)
연도별 반복	최대 O(10000)회
전체 시간 복잡도	O(Y * K)

---

5. 개선할 점 및 대체 방법

✅ 개선 가능성

• coor 리스트는 매년 갱신되어야 하므로 Queue보다는 List로 사용하는 것이 적절
• DFS보다 BFS가 깊이 제한 없이 처리 가능하므로 선택한 것도 적절함

🔄 대체 방법

• DFS로 구현도 가능하지만, 재귀 깊이에 주의 필요
• BFS를 통해 연도별 상태를 별도 저장하면 시각화도 가능