백준 2573번: 빙산 [DFS][BFS][탐색][그래프]-Java

 

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

2573번: 빙산

 

1. 1년씩 흐를때 마다 빙산의 높이 계산

2. 그 빙산들이 두 덩어리 인지 체크

 

요 2가지만 잘 챙기면됨.. 

 

<Java 코드>

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

public class Main {

	public static int dx[] = { 0, 1, 0, -1 };
	public static int dy[] = { 1, 0, -1, 0 };
	public static int N, M, ans = 0;
	public static int map[][];
	public static boolean visit[][];
	public static boolean divFlag = false;
	public static ArrayList<Iceberg> list; // 현재 빙산인 부분들을 관리하는 list

	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];
		list = new ArrayList<Iceberg>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] > 0) {
					Iceberg ice = new Iceberg(i, j, map[i][j]);
					list.add(ice);
				}
			}
		}

		while (true) {

			if (divFlag || list.size() == 0) {
				break;
			}

			ans++;
			// 1년 후 빙산 높이 계산
			ArrayList<Iceberg> newList = new ArrayList<Iceberg>();
			
			int newMap[][] = new int[N][M];
			for (int i = 0; i < list.size(); i++) {
				Iceberg ice = list.get(i);
				int cnt = countSea(ice); // 바다와 접한 부분 계산
				int newH = ice.h - cnt < 0 ? 0 : ice.h - cnt;
				if(newH > 0)
					newList.add(new Iceberg(ice.x, ice.y, newH));
				newMap[ice.x][ice.y] = newH;
			}

			// 최신화
			list = new ArrayList<>(newList);
			map = newMap;
//			print();

			visit = new boolean[N][M];
			// 빙산이 두 덩어리인지 확인
			if(list.size()>0)
				dfs(list.get(0));

			for (int i = 1; i < list.size(); i++) {
				if (!visit[list.get(i).x][list.get(i).y]) {
					divFlag = true;
					break;
				}
			}
		}

		if (!divFlag || list.size() == 0)
			System.out.println(0);
		else
			System.out.println(ans);

	}

	public static void dfs(Iceberg ice) {
		visit[ice.x][ice.y] = true;
		for (int i = 0; i < 4; i++) {
			int nx = ice.x + dx[i];
			int ny = ice.y + dy[i];

			// 범위 체크
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;

			// 이미 들른곳인지?
			if (visit[nx][ny])
				continue;

			// 빙산과 접한 면인지?
			if (map[nx][ny] > 0) {
				dfs(new Iceberg(nx, ny, map[nx][ny]));
			}

		}

	}

	public static int countSea(Iceberg ice) {
		int sum = 0;
		for (int i = 0; i < 4; i++) {
			int nx = ice.x + dx[i];
			int ny = ice.y + dy[i];

			// 범위 체크
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;

			// 바다와 접한 면인지?
			if (map[nx][ny] == 0)
				sum++;
		}

		return sum;
	}
	
	public static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j]+"\t");
			}
			System.out.println();
		}
	}

}

class Iceberg {
	int x;
	int y;
	int h;

	public Iceberg(int x, int y, int h) {
		this.x = x;
		this.y = y;
		this.h = h;
	}
}