백준 2573. 빙산

백준 2573. 빙산

시뮬레이션 문제

---

문제 분석

• 빙산이 2차원배열에 표시됨
• 빙산의 각 부분별 높이 정보는 각 칸의 양의 정수로 주어짐
• 0은 바다.
• 바닷물에 접해있는 부분의 높이는 더 빨리 줄어든다
  • 1년마다 동서남북 네 방향으로 붙어있는 0의 저장된 칸의 개수 만큼 줄어든다
• 각 칸의 높이는 0보다 더 줄어들지 않는다
• 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간을 구하는 프로그램 작성하기

입력

첫줄에 행과열의 개수 N, M이 주어짐 (3<= N, M <= 300)

그 다음 N줄에 높이정보 M개가 주어짐. 각 칸의 높이는 0이상 10이하

배열에서 빙산이 차지하는 칸의 개수, 즉 1이상의 정수가 들어가는 칸의 개수는 10000개 이하이다.

-> 빙산의 크기는 10000 이하이다

배열의 첫번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

-> 테두리는 항상 0이다. 바다는 항상 존재함

출력

첫 줄에 빙산이 분리되는 최초의 시간을 출력한다

만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

예제 분석

1)

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

테두리는 항상 0임

(1,1)을 보면 상하좌우에 0이 2칸 있음 -> 2만큼 줄어드므로 내년에 0이된다 (1,2) : 상하에 2칸. 4->2 (1,3) : 위쪽에 한칸. 5->4 … 이런식으로 1년이 지나면

0 0 0 0 0 0 0			0 0 0 0 0 0 0 
0 0 2 4 1 0 0			0 0 0 3 0 0 0
0 1 0 1 5 0 0			0 0 0 0 4 0 0
0 5 4 1 2 0 0			0 3 2 0 0 0 0
0 0 0 0 0 0 0			0 0 0 0 0 0 0
1년뒤					2년뒤

1년뒤까지 한덩어리였다가

2년뒤에 3덩어리로 분리되므로, 2을 출력

---

알고리즘

매년 빙산이 녹는걸 보고 -> 빙산이 몇개있는지 체크를 반복한다

빙산이 녹는건 각 좌표에서 상하좌우에 0이 몇개있는지 체크 후 뺴주면 됨

빙산이 몇덩어리가 있는지를 체크하는건 BFS, 그중에서도 Blood-fill을 이용하면 가능하다

1. 전처리
	- N, M 입력받기
	- 맵 정보 입력받기
2. 결과가 나올때 까지 무한 반복
	2-1. 빙하를 녹이고 시간을 1년 보낸다
	2-2. 빙산 덩어리 개수 세기
		- BFS 함수로 visited 배열에 방문 여부만 기록함
	2-3. 빙하의 개수가 0개라면, 0을 출력 후 종료
	2-4. 2개 이상이라면, 걸린 시간을 출력 후 종료
	2-5. 1덩어리라면 계속 루프
'

필요 변수

• int N, M (3<=N,M<=300)
• int map[300][300] : 맵은 최대 4byte * 300 * 300 = 360,000byte = 360kb 이므로 충분함
• bool visited[300][300] : 해당 좌표에 방문했는지 체크용
• int direct[4][2] : 상하좌우 이동용

---

소스코드

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 301;

int N, M;
int map[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 }; // →↓←↑

void Input() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		}
	}

}

// map을 수정하지 않고, visited 방문 여부만 기록
void BFS(int start_y, int start_x) {
	queue< pair<int, int> > qu;

	qu.push({ start_y, start_x });
	visited[start_y][start_x] = true;

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.first;
			int dx = direct[t][1] + now.second;

			if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue;
			if (visited[dy][dx] == true) continue; // 이미 방문한곳
			if (map[dy][dx] == 0) continue; // 물

			visited[dy][dx] = true;
			qu.push({ dy, dx });
		}
	}
}

// 1년동안 빙하가 녹는 과정을 처리하는 함수
void meltIcebergs() {
	int melt_amount[MAX_SIZE][MAX_SIZE] = { 0 };

	// 현재 map 상태를 기준으로 각 빙하가 얼마나 녹을지 계산
	for (int y = 1; y <= N - 2; y++) {
		for (int x = 1; x <= M - 2; x++) {
			if (map[y][x] > 0) {
				// 상하좌우에 0이 몇개있는지 체크
				int sea_neighbors = 0;
				for (int t = 0; t < 4; t++) {
					int dy = y + direct[t][0];
					int dx = x + direct[t][1];

					if (map[dy][dx] == 0) 
						sea_neighbors++;
				}

				melt_amount[y][x] = sea_neighbors;
			}
		}
	}
	// 계산된 값을 바탕으로 map에 한번에 적용
	for (int y = 1; y <= N - 2; y++) {
		for (int x = 1; x <= M - 2; x++) {
			map[y][x] = max(0, map[y][x] - melt_amount[y][x]);
		}
	}
}

// 빙하 덩어리가 몇개인지 세는 함수
int countComponents() {
	memset(visited, 0, sizeof(visited));
	int components = 0;
	for (int y = 1; y <= N - 2; y++) {
		for (int x = 1; x <= M - 2; x++) {
			if (map[y][x] > 0 && !visited[y][x]) {
				components++;
				BFS(y, x);
			}
		}
	}
	return components;
}

void Solve() {
	Input();

	int years = 0;
	while (true) {
		// 1. 빙하를 녹이고 시간을 1년 보냄
		years++;
		meltIcebergs();

		// 2. 1년 후 빙하 덩어리 개수 체크
		int components = countComponents();

		// 3. 전부 녹아서 덩어리가 없다면, 0을 출력 후 종료
		if (components == 0) {
			cout << "0";
			return;
		}

		// 4. 덩어리가 2개 이상으로 나눠졌다면, 걸린 시간을 출력 후 종료
		if (components >= 2) {
			cout << years;
			return;
		}
		// 5. 덩어리가 한개라면 계속 루프
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

#ifdef _DEBUG
	freopen_s(new FILE*, "input.txt", "r", stdin);
#endif
	Solve();
	return 0;
}

이전까지 문제를 풀때는 덩어리 개수를 체크할 때, map에서 0으로 지우는 방법을 통해 개수를 세는 방식을 썼다

이번에는 countComponents 함수와 BFS 함수를 분리시켜서

countComponents에서 빙산의 시작점을 확인해서 BFS를 호출하고,

BFS에서 연결된 빙산을 모두 visited로 체크하는 방법을 사용했다

덕분에 별도의 백업용 map 사용하지 않아 memset을 쓰지도 않았고, 메모리도 절약 가능했다