[백준/BOJ] 2573번 빙산 (C++)

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

2573번: 빙산

문제의 조건을 정리하며 차례대로 구현하면 어렵지 않게 해결할 수 있는 BFS 문제였다. 

 

1. map 입력을 받는다.
2. map[i][j] > 0, 현재 빙산과 접하는 바닷물의 수를 구하고, 이를 현재 빙산에서 빼준다.
(그 뺀 값이 음수라면 0으로 바꿔주기)
3. 모든 map에 대해 2번 작업을 완료했다면, BFS를 통해 분리된 덩어리의 수를 구한다.
4. 분리된 덩어리의 수가 2보다 크거나 같다면 종료, 아니라면 2번 작업으로 돌아간다.
+ 모든 빙산이 녹아있는 경우 0을 리턴한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

struct Pos {
	int x, y, melt;
};

int n, m, time;
int map[301][301];
bool visit[301][301];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void BFS(int sx, int sy) {
	queue<pair<int, int> > q;
	q.push({ sx, sy });
	visit[sx][sy] = true;
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(!visit[nx][ny] && map[nx][ny] > 0) {
				q.push({ nx, ny });
				visit[nx][ny] = true;
			}
		}
	}
}

int melting(int x, int y) {
	int res = 0;
	
	for(int i = 0; i < 4; i++) {
		if(map[x + dx[i]][y + dy[i]] == 0) res++;
	}
	
	return res;
}

int main(void) {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> map[i][j];			
		}
	}
	
	bool flag = true;
	while(flag) {
		time++;
		flag = true;
		memset(visit, false, sizeof(visit));
		vector<Pos> v;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(map[i][j] > 0) {
					v.push_back({ i, j, melting(i, j) });
				}
			}
		}
		
		if(v.empty()) {
			cout << "0";
			exit(0);
		}
		
		for(int i = 0; i < v.size(); i++) {
			int x = v[i].x;
			int y = v[i].y;
			int melt = v[i].melt;
			map[x][y] -= melt;
			if(map[x][y] < 0) map[x][y] = 0;
		}
		
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(map[i][j] > 0 && !visit[i][j]) {
					BFS(i, j);
					cnt++;
					if(cnt >= 2) {
						flag = false;
						break;
					}
				}
			}
			if(!flag) break;
		}
	}
	
	cout << time;
}