[BOJ] 빙산

[BOJ] 빙산

Problem URL : 빙산

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX 301

using namespace std;

int N, M;
bool visit[MAX][MAX];
int map[MAX][MAX];
int tmpMap[MAX][MAX];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

bool outRange(int x, int y) {
	if (x < 0 || x >= N || y < 0 || y >= M) {
		return true;
	}
	return false;
}

// 빙하 주의 0의 개수 반환
int zeroCnt(int x, int y) {
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if (outRange(nx,ny)) continue;
		if (map[nx][ny] == 0) cnt++;
	}
	return cnt;
}

// 빙하를 녹인다
void meltIce(int x, int y) {
	int zCnt = zeroCnt(x, y);
	tmpMap[x][y] = map[x][y] - zCnt;
	if (tmpMap[x][y] < 0) tmpMap[x][y] = 0;
}

// 연결된 빙하를 다 탐색한다
void visitLinkedIce(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	visit[x][y] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		meltIce(x, y);
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if (outRange(nx,ny) || visit[nx][ny] || map[nx][ny] == 0) continue;
			q.push({ nx,ny });
			visit[nx][ny] = true;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	queue<pair<int, int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	int year = 0;

	while (1) {
		memset(tmpMap, 0, sizeof(tmpMap));
		memset(visit, false, sizeof(visit));
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visit[i][j] && map[i][j] != 0) {
					visitLinkedIce(i, j);
					cnt++;
				}
			}
		}

		if (cnt >= 2) {
			break;
		}else if (cnt == 0) {
			year = 0;
			break;
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				//임시로 기록해놓은 녹은 빙하값을 원래 map에 기록
				map[i][j] = tmpMap[i][j];
			}
		}
		year++;
	}

	cout << year << "\n";

	return 0;
}