백준 2573번 빙산 C++

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

 

bfs를 이용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using ll = long long;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

struct hashFunction
{
	size_t operator()(const pair<int, int>& x) const
	{
		return x.first *1000 + x.second;
	}
};

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

	int n, m;
	cin >> n >> m;
	vector<vector<int>> board(n, vector<int>(m));
	vector<vector<bool>> found(n, vector<bool>(m, false));
	unordered_set<pair<int, int>, hashFunction> us;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) continue;
			us.insert({ i,j });
		}
	}
	int year = 0;
	while (true) {
		vector<pair<int, int>> melts;
		queue<pair<int, int>> q;
		q.push({ us.begin()->first, us.begin()->second });
		found[us.begin()->first][us.begin()->second] = true;
		while (!q.empty()) {
			auto curr = q.front();
			q.pop();
			int meltCnt = 0;
			for (int i = 0; i < 4; i++) {
				int nextRow = curr.first + dRow[i];
				int nextCol = curr.second + dCol[i];
				if (nextRow < 0 || nextRow >= n) continue;
				if (nextCol < 0 || nextCol >= m) continue;
				if (found[nextRow][nextCol]) continue;
				if (board[nextRow][nextCol] == 0) {
					meltCnt++;
					continue;
				}
				found[nextRow][nextCol] = true;
				q.push({ nextRow,nextCol });
			}
			board[curr.first][curr.second] = max(board[curr.first][curr.second] - meltCnt, 0);
			if (board[curr.first][curr.second] == 0) melts.push_back({ curr.first,curr.second });
		}
		bool isAllFound = true;
		for (auto a : us) {
			if (found[a.first][a.second] == false) isAllFound = false;
		}
		for (auto a : us) {
			found[a.first][a.second] = false;
		}
		for (auto a : melts) {
			us.erase({ a.first,a.second });
		}
		if (!isAllFound) break;
		if (us.size() == 0) {
			year = 0;
			break;
		}
		year++;
	}
	cout << year;
};