백준 2573번 빙산

문제

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

코드

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


#define MAX 300
int n, m;

vector<vector<int>> map(MAX, vector<int>(MAX, 0));

int bfs()
{
	vector<vector<int>> temp = map;
	bool found = false;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (temp[i][j] != 0)
			{
				found = true;
				queue<pair<int, int>> q;
				q.push({ i,j });

				while (!q.empty())
				{
					int y = q.front().first;
					int x = q.front().second;
					q.pop();
					int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

					for (int k = 0; k < 4; k++)
					{
						int new_y = y + dir[k][0];
						int new_x = x + dir[k][1];

						if (temp[new_y][new_x] != 0)
						{
							temp[new_y][new_x] = 0;
							q.push({ new_y,new_x });
						}
					}
				}
			}
			if (found) break;
		}
		if (found) break;
	}
	
	if (!found)
		return 2;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (temp[i][j] != 0)
				return 1;
		}
	}
	return 0;
}

void afterYear()
{
	vector<vector<int>> temp = map;
	int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] != 0)
			{
				int cnt = 0;
				for (int k = 0; k < 4; k++)
				{
					int y = i + dir[k][0];
					int x = j + dir[k][1];

					if (map[y][x] == 0)
						cnt++;
				}
				temp[i][j] =map[i][j]- cnt;
				if (temp[i][j] < 0)
					temp[i][j] = 0;
			}
		}
	}
	map = temp;

}


int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
		}
	}
	int answer = 0;
	while (1)
	{
		answer++;
		afterYear();

		if (bfs()==1)
		{
			cout << answer;
			break;
		}	
		else if(bfs() == 2)
		{
			cout << 0;
			break;
		}
	}
	
}

풀이

크게 어렵지 않은 구현문제였습니다.

1년이 지날때마다 사방의 0의 개수를 구한뒤에 그만큼 빼주고 bfs를 사용해서 땅이 2개 이상인지를 검사했습니다