[알고리즘][DFS][2573] 빙산

문제

https://www.acmicpc.net/problem/2573

풀이

1. 빙산이 몇 조각인지 dfs로 탐색한다.

2. 0 조각일 경우, 알고리즘을 마친다. 한 조각일 경우,  빙산 녹이는 함수를 돌린다. 두 조각 이상일 경우, result를 출력하고 끝낸다.

3. 빙산을 녹이는 함수는 사방의 함수를 탐색하여 counting하여 temp배열에 넣는다.

4. 빙산 배열에서 temp배열에 카운팅된 수들을 빼준다.

코드

package algorithm_DFS;
 
import java.util.Scanner;
 
public class q_2573 {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    public static int[][] iceberg;
    static int[][] melting_layer;
    static boolean[][] checked= new boolean[301][301];
    static int[][] temp;
    static int cnt = 0;
    public static int melting_ice(int x, int y) {
        int cnt = 0;
        for(int i=0;i<4;i++) {
            int mx = x + dx[i];
            int my = y + dy[i];
            if(mx<0 || mx>=n || my<0 || my>=m) continue;
            if(iceberg[mx][my]<=0) {
                if(iceberg[x][y]>0) {
                    ++cnt;
                }
            }
        }
        return cnt;
    }
    
 
    
    public static int component_num() {
        int comp = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(!checked[i][j] && iceberg[i][j]>0) {
                    ++comp;
                    dfs(i,j);
                }
            }
        }
        return comp;
    }
    
    public static void dfs(int x, int y) {
        checked[x][y] =true;
        
        for(int i=0;i<4;i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(!checked[nx][ny] && iceberg[nx][ny]>0) {
                dfs(nx, ny);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        int result = 0;
        
        iceberg = new int[n][m];
        temp = new int[n][m];
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                iceberg[i][j] = scan.nextInt();
            }
        }
        
        
        int tmp = 0;
        while((tmp = component_num()) < 2) {
            if(tmp==0) {
                result = 0;
                break;
            }
            ++result;
            checked = new boolean[301][301];
            
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    if(iceberg[i][j]>0) {
                        temp[i][j]=melting_ice(i, j);    
                    }
                }
            }            
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    iceberg[i][j]-= temp[i][j];
                }
            }
            
        }
        System.out.println(result);
 
    }
 
}