백준2573번 - 빙산

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

2573번: 빙산

문제풀이 

먼저 빙산이 몇 덩어리 인지는 DFS 로 계산을 하였습니다.

 

메인 코드에서 DFS 에 들어가는 횟수가 곧 빙산의 갯수입니다.

 

만약 모든 빙산이 상, 하, 좌, 우로 연결되어 있다면 메인에서 DFS 한번 들어가는 것만으로 모든 빙산을 돌고 나올겁니다.

 

 

두번째로 melt 배열을 만들어 녹는 빙산의 높이를 저장하였습니다.

 

높이는 DFS 를 한번 돌때마다 해당 좌표의 상, 하, 좌, 우를 확인하여 0 인 값이 있으면 melt++ 를 하였습니다.

 

 

그리고 빙산의 갯수를 세어 0 개면 0 출력하고 빙산의 갯수가 2개 이상이면 년수를 출력했습니다.

 

만약 빙산이 아직 한 덩어리라면 높이를 빼주는 melting 함수를 만들었습니다.

 

2중 for문을 돌면서 빙산의 원래 높이인 map 배열에서 녹은 높이인 melt 배열을 빼줍니다.

 

그리고 빼준 값이 음수라면 0으로 바꿔줍니다.

 

이 함수에서 다음 빙산의 갯수를 체크하기 위해 visited 배열과 melt 배열을 초기화해주었습니다.

 

 

import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[][] arr;
	static int N, M;
	static int[] dy = { -1, 0, 1, 0 };
	static int[] dx = { 0, 1, 0, -1 };

	static boolean[][] visited;
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		arr = new int[N][M];
		visited = new boolean[N][M];
		ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		dfs();
	}

	public static void dfs() {

		int ans = 0;
		while (true) {
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (!visited[i][j] && map[i][j] != 0) {
						go(i, j);
						cnt++;
					}
				}
			}
			if (cnt == 0) {
				System.out.println(0);
				break;
			} else if (cnt >= 2) {
				System.out.println(ans);
				break;
			}
			melting();
			ans++;
		}

	}

	private static void go(int y, int x) {
		visited[y][x] = true;
		for (int k = 0; k < 4; k++) {
			int ny = y + dy[k];
			int nx = x + dx[k];
			if (ischecked(ny, nx)) {
				if (map[ny][nx] == 0) {
					arr[y][x]++;
				}
				if (!visited[ny][nx] && map[ny][nx] != 0) {
					go(ny, nx);
				}
			}
		}
	}

	private static void melting() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] -= arr[i][j];
				if (map[i][j] < 0) {
					map[i][j] = 0;
				} else {
					visited[i][j] = false;
					arr[i][j] = 0;
				}

			}
		}
	}

	private static boolean ischecked(int my, int mx) {
		if (my >= 0 && my < N && mx >= 0 && mx < M) {
			return true;
		}
		return false;
	}

}