[백준 2573] 빙산

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

2573번: 빙산

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int N, M;
int A[300 + 2][300 + 2];
int S[300 + 2][300 + 2];
int visited[300 + 2][300 + 2];

struct _st
{
	int x, y;
};

std::queue<_st> Q;

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };



void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &A[i][j]);
		}
	}
}


int chk(int x, int y)
{
	int zero = 0;

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
		if (A[nx][ny] == 0) zero++;
	}
	return zero;
}



void melt()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (A[i][j] == 0) continue;
			int cnt = chk(i, j);
			S[i][j] = (A[i][j] - cnt > 0) ? A[i][j] - cnt : 0;
		}
	}
	std::fill(&A[0][0], &A[0][0] + sizeof(A) / sizeof(int), 0);
	memcpy(A, S, sizeof(S));
	std::fill(&S[0][0], &S[0][0] + sizeof(S) / sizeof(int), 0);
}



void get_iceberg(int x, int y)
{
	Q = {};
	Q.push({ x, y });
	visited[x][y] = 1; 

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			if (A[nx][ny] == 0) continue;
			if (visited[nx][ny]) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
}




int FF()
{
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	int group = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j]) continue;
			if (A[i][j] == 0) continue;
			get_iceberg(i, j);
			group++;
		}
	}
	return group;
}


int simul()
{
	int days = 0;
	while (1) {
		melt();
		days++;
		int cnt = FF();
		if (cnt >= 2) return days;
		if (cnt == 0) return 0;		// 빙산 그룹이 하나도 안만들어짐, 즉 얼음이 다 녹아버림 
	}
}


int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

스근하게 풀어봄... 

Flood-Fill로 완전탐색 하고 최대 300 * 300 맵이 될 수 있어서 BFS 사용했다. 

 

---

++22.11.09 다시 풀어봤는데 이전 코드가 더 깔끔한듯... ?

그래도 남겨본다.

격자공간 다 탐색 안하고, 녹고 남은 빙산의 높이가 0보다 큰 곳들만 벡터에 담아서 탐색하게 했다. 만약 벡터 사이즈가 0이면 다 녹았다는 것이므로 곧바로 0을 리턴한다.

덕분에 실행시간은 좀 줄어든 것 같다. 

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
int R, C;	// 300 * 300
int board[300 + 2][300 + 2];
int tmp[300 + 2][300 + 2];
int visited[300 + 2][300 + 2];

struct _st
{
	int x, y;
};
std::queue<_st> Q;
std::vector<_st> V;

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &board[i][j]);
		}
	}
}


void del_ice()
{
	memset(tmp, 0, sizeof(tmp));
	memcpy(tmp, board, sizeof(tmp));
	V.clear();

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 0) continue;
			int cnt = 0;
			for (int p = 0; p < 4; p++) {
				int nx = i + dir_x[p];
				int ny = j + dir_y[p];

				if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
				if (board[nx][ny] == 0) cnt++;
			}
			tmp[i][j] = (tmp[i][j] - cnt < 0) ? 0 : tmp[i][j] - cnt;	// 0보다 더 줄어들지는 않는다
			if (tmp[i][j] != 0) V.push_back({ i, j });
		}
	}
	memcpy(board, tmp, sizeof(tmp));
}


void BFS(int x, int y)
{
	Q = {};

	Q.push({ x, y });
	visited[x][y] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 0) continue;

			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
}


int simul()
{
	int time = 1;
	while (1) {
		del_ice();						// 빙산이 줄어듦
		if (V.size() == 0) return 0;	// 빙산이 다 녹을때까지 분리되지 않음 

		int ice_berg = 0;
		memset(visited, 0, sizeof(visited));
		for (_st v : V) {
			if (visited[v.x][v.y]) continue;
			BFS(v.x, v.y);				// 분리되었는지 안분리되었는지 
			ice_berg++;
		}
		if (ice_berg >= 2) return time;
		time++;
	}
}

int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}