[BOJ 2573] 빙산

[풀이 코드]

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

public class 빙산 {
	static int N, M;
	static int[][] arr;
	static boolean[][] v;
	static List<Point> iceList;
	static int year, iceCount;
	static boolean isDivide;
	static int[] dr = {0, 0, 1, -1};
	static int[] dc = {1, -1, 0, 0};
	static int[][] zeroNumber;
	
	
	static class Point {
		int x, y;
		Point(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	public static void main(String[] args) throws Exception {
		// 빙산 1, 바다 0
		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());
		arr = new int[N][M];
		iceList = new ArrayList<Point>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine().trim());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j] > 0) iceList.add(new Point(i, j));
			}
		}
		
		year = 0;
		isDivide = false;
		zeroNumber = new int[N][M];
		while(!isDivide && !iceList.isEmpty()) {
			// 각 빙산 위치마다 0의 개수를 센다
			for(Point p : iceList) {
				int cnt = zeroCount(p);
				zeroNumber[p.x][p.y] = cnt; 
			}

			// 각 빙산을 녹인다.
			for(int i=0; i<iceList.size(); i++) {
				Point p = iceList.get(i);
				if(arr[p.x][p.y] - zeroNumber[p.x][p.y] <= 0) {
					arr[p.x][p.y] = 0;
					iceList.remove(i--);
				}else {
					arr[p.x][p.y] -= zeroNumber[p.x][p.y]; 
				}
				zeroNumber[p.x][p.y] = 0;
			}

			// 빙산 덩어리 갯수를 센다.
			iceCount = 0;
			v = new boolean[N][M];
			for(Point p : iceList) {
				if(!v[p.x][p.y]) {
					dfs(p.x, p.y);
					iceCount++;
				}
			}
			
			if(iceCount >= 2) isDivide = true;
			year++;
		}
		
		if(iceList.isEmpty()) {
			System.out.println(0); return;
		}
		System.out.println(year);
		
	}
	
	private static int zeroCount(Point p) {
		int num = 0;
		for(int d=0; d<4; d++) {
			int nr = p.x + dr[d];
			int nc = p.y + dc[d];
			if(nr<0 || nr>=N || nc<0 || nc>=M) continue;
			if(arr[nr][nc] == 0) num++;
		}
		
		return num;
	}
	
	private static void dfs(int r, int c) {
		v[r][c] = true;
		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr<0 || nr>=N || nc<0 || nc>=M || v[nr][nc] || arr[nr][nc] <= 0) continue;
			dfs(nr, nc);
		}
	}
	
}

시뮬레이션 + 4방탐색 문제다.

풀이시간은 53분이 걸렸다.

56%에서 시간초과가 나서, 계속 문제를 다시 읽어본 다음 두 덩어리 이상으로 나누어지지 않는 경우의 수를 놓쳤다는 걸 알게됐다.
그래서 while문 탈출 조건에 iceList가 다 비어있을 경우를 추가하고, 결과 값도 수정했다.