[BJ2573] 빙산

 백준 - 빙산 

문제 링크

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

2573번: 빙산

 

문제 입출력

4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

0

5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0

2

 

문제 풀이

package problem.BJ;


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


public class BJ2573_빙산 {
	static int ans, N, M;
	static int[][] map, mapTemp;
	static boolean[][] visit;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		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];
		mapTemp = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) mapTemp[i][j] = Integer.parseInt(st.nextToken());
		}

		// 초기화
		ans = 0;
		copyMap(mapTemp, map);

		// 탐색
		while (true) {

			// 덩어리 갯수 확인하기
			int max = 0;
			visit = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] == 0) continue;
					if (visit[i][j]) continue;
					dfs(i, j);
					max++;
				}

			}

			// 만약 덩어리가 2개 이상이라면 break
			if (max >= 2) break;

			// 모두 녹았으면 break
			if (allMelt() == N * M) {
				if (max < 2) ans = 0; // 모두 녹았는데도 덩어리가 2개 미만이면
				break;
			}

			melt();

			ans++; // 시간 세기
			copyMap(map, mapTemp);

		}

		// 출력
		System.out.println(ans);

	} // end main


	// 주변 바다에 의해 빙산이 녹는 함수
	private static void melt() {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (map[y][x] == 0) continue;

				for (int d = 0; d < 4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];

					if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
					if (mapTemp[ny][nx] != 0) continue; // 연마다 녹으므로 값이 변경되지 않는 값을 확인

					if (map[y][x] > 0) map[y][x] -= 1;
				}

			}

		}

	} // end melt


	// 덩어리 확인하는 함수
	private static void dfs(int y, int x) {
		visit[y][x] = true;

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visit[ny][nx]) continue;
			if (map[ny][nx] == 0) continue;

			dfs(ny, nx);
		}

	} // end dfs


	// 다 녹았는지 확인하는 함수
	private static int allMelt() {
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) if (map[i][j] == 0) sum++;
		}

		return sum;
	} // end allMelt


	private static void copyMap(int[][] src, int[][] tgt) {
		for (int i = 0; i < N; i++) tgt[i] = src[i].clone();
	} // end copyMap
}

• dfs 를 이용해서 풀 수 있습니다.
• 해당 덩어리들이 몇 개인지 dfs() 를 이용하여 수를 셉니다.
  • dfs() 는 깊이를 탐색하므로
• 델타를 이용하여 주변 바다에 의해서 빙산을 녹이는 함수를 만듭니다.
• 여기서 연마다 녹으므로 값이 변경되어 들어간 map 을 넣으면 0으로 되어버린 빙산까지 세버려 잘못된 값이 됩니다.
• 따라서 mapTemp 에 저장하여 해당 값을 비교하여 빙산을 녹입니다.

 

 

 

 

 

 

 

 

 

# 백준 빙산 dfs java # 백준 빙산 java

---