BOJ2573 빙산

<Solution>

1. DFS로 몇덩어리인지 검사

2. BFS로 얼음녹여

3. 반복

4. return 되는 경우는 (1) 덩어리가 2 이상 되는경우 (2) 얼음이 다 녹았는데 (1)인 경우로 return 안된 경우

 

<Source Code>

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

public class BOJ2573_빙산 {
	
	static int[][] map, map_copy;
	static int[][] visit;
	static Queue<pair> q;
	static int year = 0, N, M, lump;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		map_copy = new int[N][M];
		q = new LinkedList<pair>();
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				int number = Integer.parseInt(st.nextToken());
				if(number != 0) {
					q.add(new pair(i,j));
				}
				map[i][j] = number;
				map_copy[i][j] = number;
			}
		}
		while(lump < 2) {
			visit = new int[N][M];
			// 1. DFS로 몇 덩어리인지 검사
			lump = 0;
			for(int i = 1; i < N-1; i++) {
				for(int j = 1; j < M-1; j++) {
					if(map[i][j] == 0 || visit[i][j] == 1)
						continue;
					lump++;
					dfs(i, j);
				}
			}
			if(lump >= 2) {
				System.out.print(year);
				return;
			}
			// 2. BFS로 얼음 녹이기
			year++;
			bfs();
			// map_copy -> map
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(map_copy[i][j] != 0)
						q.add(new pair(i,j));
					map[i][j] = map_copy[i][j];
				}
			}
			// 다 녹았는데 lump >= 2 인 경우에 안걸렸으면 그냥 0 출력
			if(q.size() == 0) {
				System.out.print(0);
				return;
			}
		}
	}
	
	private static void bfs() {
		while(!q.isEmpty()) {
			pair p = q.poll();
			int zero_cnt = 0;
			for(int di = 0; di < 4; di++) {
				int nn = p.n + dn[di];
				int mm = p.m + dm[di];
				if(nn >= N || nn < 0 || mm >= M || mm < 0)
					continue;
				if(map[nn][mm] == 0)
					zero_cnt++;
			}
			map_copy[p.n][p.m] -= zero_cnt;
			if(map_copy[p.n][p.m] < 0)
				map_copy[p.n][p.m] = 0;
		}
	}

	static int[] dn = {0,1,0,-1};
	static int[] dm = {-1,0,1,0};
	
	private static void dfs(int i, int j) {
		visit[i][j] = 1;
		for(int di = 0; di < 4; di++) {
			int nn = i + dn[di];
			int mm = j + dm[di];
			if(nn >= N || nn < 0 || mm >= M || mm < 0)
				continue;
			if(map[nn][mm] == 0 || visit[nn][mm] == 1)
				continue;
			dfs(nn, mm);
		}
	}

	static class pair{
		int n;
		int m;
		public pair(int n, int m) {
			super();
			this.n = n;
			this.m = m;
		}
	}
}

더 깔끔하게 다듬고 싶긴하지만 일단... 풀었으니!! 3년전에는 시간초과로 넘어갔던 문제 흠 비교도 나중에~