[BOJ] 2573 빙산

 

 

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] 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 result = 0;
		while(true){
			int cnt = 0;
			boolean[][] visit = new boolean[n][m];
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(map[i][j]!=0 && !visit[i][j]) {
						cnt++;
						Queue<int[]> q = new LinkedList<>();
						q.offer(new int[] {i,j});
						visit[i][j] = true;
						while(!q.isEmpty()) {
							int[] curr = q.poll();
							for(int d=0;d<4;d++) {
								int nr = curr[0] + dr[d];
								int nc = curr[1] + dc[d];
								if(nr<0 || nr>=n || nc<0 || nc>=m || visit[nr][nc]) continue;
								if(map[nr][nc]>0) {
									visit[nr][nc] = true;
									q.offer(new int[] {nr,nc});
								}
							}
						}
					}
				}
			}
			if(cnt==0) {
				System.out.println(0);
				return;
			}
			if(cnt>=2) {
				System.out.println(result);
				return;
			}
			int[][] melt = new int[n][m];
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(map[i][j]>0) {
						for(int d=0;d<4;d++) {
							int nr = i + dr[d];
							int nc = j + dc[d];
							if(nr<0 || nr>=n || nc<0 || nc>=m) continue;
							if(map[nr][nc]==0) melt[i][j]++;
						}
					}
				}
			}
			for(int i=0;i<n;i++) { 
				for(int j=0;j<m;j++) {
					if(melt[i][j]>0) map[i][j] -= melt[i][j];
					if(map[i][j]<0) map[i][j] = 0;
				}
			}
			result++;
		}
	}
}