[BaekJoon] 2573 빙산 (Java)

1.  문제 링크

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

2.  문제

요약

• 빙산을 2차원 배열에 표시하고 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장됩니다.
• 빙산 이외의 바다에 해당되는 칸에는 0이 저장됩니다.
• 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어듭니다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않습니다.
• 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있습니다.
• 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 문제입니다.
• 만약 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 0을 출력합니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 300보다 작거나 같은 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N, M이 주어지고 두 번째 줄부터 N개의 줄에는 0보다 크거나 같고 10보다 작거나 같은 배열의 각 행을 나타내는 M개의 정수가 주어집니다.
  • 배열에서 빙산이 차지하는 칸의 개수는 10,000개 이하입니다.
  • 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워집니다.
• 출력: 첫 번째 줄에 빙산이 분리되는 최초의 시간(년)을 출력합니다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력합니다.

3.  소스코드

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

public class Main {
	static int N, M, mass;
	static int[][] icebergs;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};;
	static boolean[][] visited;
	static ArrayList<Integer>[] icebergLoc;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		icebergs = new int[N][M];
		icebergLoc = new ArrayList[N];
		for(int index = 0; index < N; index++) icebergLoc[index] = new ArrayList<Integer>();
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < M; col++) {
				icebergs[row][col] = scanner.nextInt();
				if(icebergs[row][col] != 0) icebergLoc[row].add(col);
			}
		}
	}
	
	static void solution() {
		int time = 0;
		while(true) {
			mass = 0;
			visited = new boolean[N][M];
			melt();
			time++;
			for(int row = 0; row < icebergLoc.length; row++) {
				for(int col = 0; col < icebergLoc[row].size(); col++) {
					int y = icebergLoc[row].get(col);
					if(!visited[row][y]) {
						mass++;
						if(mass >= 2) {
							System.out.println(time);
							return;
						}
						dfs(row, y);
					}
				}
			}
			boolean flag = true;
			for(int i = 0; i < icebergLoc.length; i++) {
				if(icebergLoc[i].size() != 0) {
					flag = false;
					break;
				}
			}
			if(flag) {
				System.out.println(0);
				return;
			}
		}
	}
	
	static void melt() {
		int[][] meltAmount = new int[N][M];
		for(int row = 0; row < icebergLoc.length; row++) {
			for(int col = 0; col < icebergLoc[row].size(); col++) {
				int x = row;
				int y = icebergLoc[row].get(col);
				int count = 0;
				for(int direction = 0; direction < 4; direction++) {
					int cx = x + dx[direction];
					int cy = y + dy[direction];
					if(cx >= 0 && cx < N && cy >= 0 && cy < M && icebergs[cx][cy] == 0) count++;
				}
				meltAmount[x][y] += count;
			}
		}
		melt(meltAmount);
	}
	
	static void melt(int[][] meltAmount) {
		for(int row = 0; row < icebergLoc.length; row++) {
			for(int col = 0; col < icebergLoc[row].size(); col++) {
				int y = icebergLoc[row].get(col);
				if(icebergs[row][y] - meltAmount[row][y] <= 0) {
					icebergs[row][y] = 0;
					icebergLoc[row].remove(Integer.valueOf(y));
					col--;
				} else {
					icebergs[row][y] -= meltAmount[row][y];
				}
			}
		}
	}
	
	static void dfs(int x, int y) {
		visited[x][y] = true;
		for(int direction = 0; direction < 4; direction++) {
			int cx = x + dx[direction];
			int cy = y + dy[direction];
			if(cx >= 0 && cx < N && cy >= 0 && cy < M) {
				if(!visited[cx][cy] && icebergs[cx][cy] != 0) dfs(cx, cy);
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 주어진 2차원 배열에서 빙산의 위치들만 저장하고 1년마다 저장한 빙산들이 얼마나 녹는지 계산하면서 빙산들이 녹았을 때 빙산이 분리되는지 DFS를 통해 확인하고 만약 그렇다면 그 때의 시간을 출력하고 그렇지 않다면 모든 빙산이 녹았는지 확인하여 그렇다면 0을 출력하고 그렇지 않다면 다시 작업을 반복합니다.
  
  
• 주어진 2차원 배열에서 빙산의 위치들을 ArrayList 배열 icebergLoc에 저장합니다.
• 빙산이 분리되는 최초의 시간을 나타내는 변수 time을 생성하고 값을 0으로 초기화합니다.
• 1년씩 늘려가면서 빙산이 모두 녹는지 혹은 빙산이 녹은 후의 2차원 배열 상황에서 빙산이 분리되는지 확인합니다.
  • 1년마다 빙산의 덩어리의 개수를 나타내는 변수 mass의 값을 0으로 초기화하고 DFS 탐색 시에 각 위치를 방문했는지 나타내는 2차원 배열 visited를 초기화합니다.
  • melt() 함수를 통해 빙산이 녹은 후의 2차원 배열 상황을 만듭니다.
    • 빙산의 각 위치가 얼만큼 녹는지 나타내는 2차원 배열 meltAmount를 만들어 icebergLoc에 있는 위치들 주변에 0의 개수를 세서 meltAmount에 값을 채우고 meltAmount와 icebergLoc에 있는 위치들을 활용하여 각 빙산이 녹은 후의 2차원 배열을 만듭니다.
    • 만약 녹은 후에 빙산의 높이가 0 이하라면 그 위치는 2차원 배열값을 0으로 만들고 icebergLoc에서 해당 위치를 제거합니다.
  • icebergLoc에 있는 각 위치들을 보고 해당 위치를 아직 방문하지 않았다면 그 위치를 시작점으로 하여 DFS 탐색을 진행하여 빙산의 덩어리의 개수를 구합니다.
    • 시작점을 잡고 DFS 탐색을 진행했을 때, DFS 탐색 시에 모든 빙산을 방문한다면 아직 한 덩어리로 존재하는 것이고, DFS 탐색을 진행한 후에도 아직 방문하지 않은 빙산이 있다면 두 덩어리 이상으로 분리된 것이기 때문에 이를 이용하여 덩어리의 개수를 구합니다.
  • 만약 빙산의 덩어리의 개수가 2개 이상이라면 그 때의 시간을 출력합니다.
  • 그렇지 않다면 모든 빙산의 높이가 0인지 확인하고 그렇다면 0을 출력하고 그렇지 않다면 시간을 1년 늘려 위 작업을 반복합니다.