백준2573 빙산

61번째 코드에서 -1 값을 넣어주는 이유는 아래 그림과 같이 (1,1)에서 동, 서, 남, 북으로 0 값이 2개라서 map[1][1] - 2 =0인데, 다음 map[1][2]에서 검사를 할 때 동, 서, 남, 북 0 값이 3개가 되니깐 -1 값을 넣어주고 다 계산해준 다음에 map에서 0보다 작을 때 0 값으로 바꿔줬습니다.

밑에 그림은 map[1][1]-2 =0 그대로 해줬을 때 다음 map[1][2]에서 검사할 때 오류를 그림으로 나타낸 거입니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static int[][] map;
    private static boolean[][] visited;
    static int[] dx = { 0, 1, 0, -1  };
    static int[] dy = { 1, 0, -1, 0 };
    private static int N;
    private static int M;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        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 cnt = 0; // 맵에서 상 , 하 , 좌 , 우 검사해서 뺴주는 값
        int result = 0; // 몇덩어리
        int minTime = 0; // 최소시간
        boolean flag = false;
 
        while (result < 2) {
            
            visited = new boolean[N][M];            
            result =0;
            for (int i = 0; i < N; i++) { // 빙산의 개수
                for (int j = 0; j < M; j++) {
                    if (map[i][j] != 0 && !visited[i][j]) {
                        visited[i][j] = true;
                        result++;
                        dfs(i, j);
                    }
                }
            }
 
            if(result>=2) break; // 두덩어리 이상이 되면 종료
            
            for (int i = 0; i < N; i++) { // 동서남북 검사해서 0이 저장된 개수만큼 줄어듬
                for (int j = 0; j < M; j++) {
                    cnt=0;
                    if (map[i][j] != 0) {
                        for (int k = 0; k < 4; k++) {
                            int nx = i + dx[k];
                            int ny = j + dy[k];
                            if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] == 0) {
                                cnt++;
                            }
                        }
                        if (map[i][j] - cnt <=0) { 
                            map[i][j] = -1; 
                        }else {
                            map[i][j] -= cnt;
                        }
 
                    }
                }
            }
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if(map[i][j] < 0) {
                        map[i][j] =0;
                    }
                }
            }
 
            minTime++;
 
    
            
 
            label: for (int i = 0; i < N; i++) { // 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않는경우
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 0) {
                        flag = true;
                    } else {
                        flag = false;
                        break label;
                    }
                }
            }
 
            if (flag) {
                System.out.println("0");
                break;
            }
 
        }
        
        if(!flag) {
            System.out.println(minTime);
        }
 
    }// end of main
 
    public static void dfs(int x, int y) {
        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && map[nx][ny] > 0) {
                visited[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }
}// end of class