[백준] 2573 빙산

1. 문제

2. 접근방법

BFS이든 DFS이든 맵을 완탐 하며 빙하를 녹이고 계속해서 한 덩어리인지 검사하는 문제

 

빙하를 녹이는 작업과 빙하가 한 덩어리로 모여 있는 작업 두가지를 해주어야 하는데

나는 이 두가지 작업을 하나의 BFS로 처리하고자 했다.

 

그 방법으로 맵을 입력 받을때 빙하의 총 갯수를 세어 놓았다가

녹이는 작업을 할 때 빙하가 녹아서 0이 되면 빙하의 갯수에서 차감 시키는 식으로 현재 총 빙하의 갯수를 알아두고

다음 녹이는 작업을 할 때 한 점에서만 bfs를 돌며 녹이는 작업을 한 횟수와 총 빙하의 갯수가 같은지 검사하는 것이다.

 

빙산의 갯수는 12

 

 

 

 

 

한점에서 시작해서 BFS를 돌며 빙산을 녹이고

몇번 녹였는지 세서 12번이 맞는지 검사

 

 

3번 상황까지 오게 되면 빙산의 갯수는 4

 

 

한 점에서 bfs를 돌리면 2번만 돌고 종료

그렇다면 다른 빙산 2개는 어딘가에 다른 덩어리로 존재한다는 것

 

 

위 와 같은 개념으로 풀이를 진행하였다.

 

3. 풀이

1. 맵을 입력 받으며 빙산의 갯수 세어놓기

2. 녹은 후에 상태를 저장할 맵과 빙산 갯수 clone

3. 원본 맵을 bfs로 돌며 녹이고 clone 맵에 상태 저장

4. 빙산이 녹은 후 0 이 되었다면 clone 빙산 갯수 -1

5. bfs를 몇번 돌았는지 원본 빙산 갯수와 비교

6. clone 맵과 빙산의 갯수를 원본으로 바꾸기

7. 빙산 갯수와 bfs 돈 횟수가 다를때까지 2 - 6 반복

8. 반복 횟수 출력

 

4. 자바 코드

package 백준;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2573빙산 {
	static int ice, N, M, year, map[][], max;
	static Point maxp = new Point();
	static boolean visit[][];
	static int dr[] = { 1, 0, -1, 0 };
	static int dc[] = { 0, -1, 0, 1 };

	/**
	 * 1. 총 얼음의 갯수를 세어둔다. 2. 1년 뒤의 변화를 위해 bfs로 어느 한 얼음부터 얼음 하나하나 방문 3. 몇번 방문한지 세고 얼음
	 * 갯수랑 비교 4. 총 얼음갯수와 방문수가 다르면 다른위치에도 얼음이 있으니 분리 되어진것이므로 year출력
	 */
	public static int oneyear(int map[][]) { // 다음년도꺼 빙산 만들기와 올해 빙산 몇개인지 검사 동시에
		int[][] c_map = map.clone();
		visit = new boolean[N][M];
		int nowice = ice; // 올해 검사용
		Queue<Point> que = new LinkedList<Point>();
		que.offer(maxp);
		int cnt = 1; // 연결된 ice갯수
		visit[maxp.x][maxp.y] = true;
		max = 0;
		while (!que.isEmpty()) {

			Point now = que.poll(); // 검사할 점
			int zero = 0; // 현재 점 주변 0
			for (int i = 0; i < 4; i++) {
				int row = now.x + dr[i];
				int col = now.y + dc[i];
				if (visit[row][col] == true)
					continue;

				if (map[row][col] == 0)
					zero++;
				else {
					que.offer(new Point(row, col));
					visit[row][col] = true;
					cnt++;
				}
			}
			
			c_map[now.x][now.y] -= zero;
			if (max < c_map[now.x][now.y]) {
				max = c_map[now.x][now.y];
				maxp.setLocation(now.x, now.y);
			}
			if (c_map[now.x][now.y] <= 0) {
				c_map[now.x][now.y] = 0;
				ice--; // 다음 년 검사를 위한 ice;
			}
		}
		if (nowice != cnt)
			return year;

		year++;
		if (ice == 0)
			return 0;
		map = c_map;
		return -1;
	}

	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];
		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) {
					ice++;
					if (max < map[i][j]) {
						max = map[i][j];
						maxp.setLocation(i, j);
					}
				}
			}
		}
		int result = 0;
		while (true) {
			result = oneyear(map);
			if (result != -1)
				break;
		}
		System.out.println(result);

	}

}

5. 마치며

이전에 연구소3 문제를 풀며 사용했던 개념을 떠올려 갯수를 카운트 하는 방식으로 푸니 어렵지 않게 해결 할 수 있었다.

역시 문제는 많이 풀어 볼수록 좋은 것 같다.

 

 

2573번: 빙산