[BOJ/Java] 2573 : 빙산

문제

 

www.acmicpc.net/problem/2573

2573번: 빙산

 

 

 

 

 

 

풀이

 

• 처음 설계

 

• 설계 수정

for문을 돌면서 바로 빙산을 녹여주고 다음 빙산으로 나니까 이전 빙산이 0까지 녹아버리는 경우 문제가 발생했다 / 따라서 해당 칸에 대한 주변 바다 개수를 melt라는 배열에 저장해준 뒤 나중에 한번에 빼주었다

 

 

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int r, c;
	static int[][] map;
	static boolean[][] visited;
	static int[][] melt;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new int[r][c];

		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < c; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int year = 0;
		while (true) {
			visited = new boolean[r][c];
			melt = new int[r][c];
			// 빙산 주변 바다 count
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					if (map[i][j] != 0) {
						melt[i][j] = seaCount(i, j);
					}
				}
			}

			// 주변 바다만큼 빙산이 녹음
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					if (melt[i][j] != 0) {
						map[i][j] -= melt[i][j];
						if (map[i][j] < 0)
							map[i][j] = 0;
					}
				}
			}

			year++;

			// 빙산이 몇 덩어리인지 count
			int count = 0;
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					if (map[i][j] != 0) {
						if (dfs(i, j)) {
							count++;
						}
					}
				}
			}

			if (count >= 2) { // 빙산 덩어리가 2개 이상이면 시간을 출력
				System.out.println(year);
				return;
			} else if (count == 0) {// 빙산이 분리되지 않고 모두 녹았으면 0을 출력
				System.out.println(0);
				return;
			}
		}
	}

	private static boolean dfs(int i, int j) {

		if (i < 0 || j < 0 || i >= r || j >= c)
			return false;

		if (!visited[i][j]) {
			visited[i][j] = true;
			if (map[i][j] != 0) {
				for (int d = 0; d < dir.length; d++) {
					int dx = i + dir[d][0];
					int dy = j + dir[d][1];
					dfs(dx, dy);
				}
				return true;
			}
		}

		return false;
	}

	private static int seaCount(int i, int j) {
		int cnt = 0;
		for (int d = 0; d < dir.length; d++) {
			int dx = i + dir[d][0];
			int dy = j + dir[d][1];
			if (map[dx][dy] == 0) {
				cnt++;
			}
		}
		return cnt;
	}
}