[ 백준 / Java ] 2573. 빙산

문제

풀이

빙하가 모두 녹거나, 빙하가 녹아서 두 부분 이상이 될때까지 반복문으로 빙하 녹이는 과정을 반복하고, 조건을 만족한다면 반복문을 break로 빠져나옵니다.

    for(int t = 1; ; t++) { // 시간을 계속 증가시키는 무한 반복문
      ...
    }

1. 모든 칸을 돌면서 주변 0의 개수를 세어줍니다. (주변 0개수를 removeCnt에 저장)
2. removeCnt의 값을 각 칸에서 빼줍니다. 이때 만약 map[i][j] - removeCnt[i][j]가 음수가 된다면, 0으로 바꿔줍니다.
3. 빙하가 모두 녹았는지 확인하고, 다 녹았다면 반복문을 빠져나갑니다.
4. 빙하가 몇 부분으로 갈라졌는지 개수를 세어줍니다. 여기서 dfs 로직이 필요합니다.

5. 빙하가 모두 녹거나, 2부분이상으로 녹을 때까지 위 로직을 반복하고, ans 값을 출력해줍니다. (ans는 초기 0으로 설정되어 있었고, 2 부분 이상으로 갈라지면 그때의 시간 값을 저장하기 때문에, 빙하가 2부분 이상으로 갈라지지 않고 모두 녹는다면 0, 2부분 이상으로 갈라진다면 그때의 시간이 저장됩니다.)

전체 코드

import java.io.*;

import java.util.*;

class Main {
  static int N, M;
  static int[] dy = {1, -1, 0, 0};
  static int[] dx = {0, 0, -1, 1};
  static int[][] map;
  static boolean[][] vis;
  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());


    vis = new boolean[N][M];
    map = new int[N][M];

    for(int i=0; i<N; ++i) {
      st = new StringTokenizer(br.readLine());
      for(int j=0; j<M; ++j) {
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    int ans = 0;
    for(int t = 1; ; t++) {
      vis = new boolean[N][M];
      int totalZeroCnt = 0;

      // 주변 0 개수 세기
      int[][] removeCnt = new int[N][M];
      for(int i=0; i<N; ++i) {
        for(int j=0; j<M; ++j) {
          if(map[i][j] == 0) continue;

          int zeroCnt = 0;
          for(int k=0; k<4; ++k) {
            int ny = i + dy[k];
            int nx = j + dx[k];
            if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;

            if(map[ny][nx] == 0) zeroCnt++;
          }

          removeCnt[i][j] = zeroCnt;
        }
      }

      // 빙하 녹이기
      for(int i=0; i<N; ++i) {
        for(int j=0; j<M; ++j) {
          map[i][j] -= removeCnt[i][j];

          if(map[i][j] < 0) map[i][j] = 0;

          if(map[i][j] == 0) {
            vis[i][j] = true;
            totalZeroCnt++;
          }
        }
      }
      boolean flag = false;
      for(int i=0; i<N; ++i) {
        for(int j=0; j<M; ++j) {
          if(!vis[i][j]) {
            flag = true;
            break;
          }
        }
      }

      if(!flag) break;

      // 개수 세기
      int cnt = 0;
      for(int i=0; i<N; ++i) {
        for(int j=0; j<M; ++j) {
          if(vis[i][j]) continue;
          if(map[i][j] == 0) continue;
          cnt++;
          dfs(i, j);
        }
      }

      if(cnt >= 2) {
        ans = t; break;
      }
    }

    System.out.println(ans);

  }

  private static void dfs(int y, int x) {
    vis[y][x] = true;

    for(int i=0; i<4; ++i) {
      int ny = y + dy[i];
      int nx = x + dx[i];

      if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
      if(vis[ny][nx]) continue;
      if(map[ny][nx] == 0) continue;

      dfs(ny, nx);
    }
  }
}