백준 2573번 : 빙산 - BFS 활용 C++

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

2573번: 빙산

접근방법[알고리즘]

1. 빙산이 몇개의 덩어리로 이루어져있는지 BFS를 이용해 개수를 센다.

2. 빙산의 개수가 2개이상이거나 0이 아니면 빙산을 한차례 녹인다.

3. 1과 2를 반복한다.

 

---

주의할 점

빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
다음 빙산에 영향을 줘서 틀린다.
빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
적용 해주어야 한다.

 

---

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[301][301] ,t;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int Count() {
	int check[301][301];
	int ans = 1;
	memset(check, 0, sizeof(check));
	queue<pair<int, int> > Q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] > 0 && check[i][j]==0) {
				check[i][j] = ans;
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];
						if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == 0) continue;
						if (check[nx][ny] == 0) {
							check[nx][ny] = ans;
							Q.push({ nx,ny });
						}
					}
				}
				ans++;
			}
		}
	}
	return ans - 1;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<pair<int, int> > Q;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] > 0) Q.push({ i,j });
		}
	}


	while (1) {
		int area = Count();
		if (area >= 2) {
			cout << t << '\n';
			return 0;
		}
		else if (area == 0) {
			cout << 0 << '\n';
			return 0;
		}

		int s = Q.size();
		//빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
		//다음 빙산에 영향을 줘서 틀린다.
		//빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
		//적용 해주어야 한다.

		vector<pair<int, int> > melt;
		for (int i = 0; i < s; i++) {
			int x = Q.front().first;
			int y = Q.front().second;
			Q.pop();

			int cnt = 0;
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny]>0) continue;
				cnt++;
			}

			if (cnt >= arr[x][y]) {
				melt.push_back({ x,y });
			}
			else {
				arr[x][y] -= cnt;
				Q.push({ x,y });
			}
		}
		for (int i = 0; i < melt.size(); i++) {
			arr[melt[i].first][melt[i].second] = 0;
		}

		t++;
	}

	return 0;
}

백준 2573번