[백준]c++/구현/2573

https://www.acmicpc.net/submit/2573/56811225

로그인

빙하 상,하,좌,우 탐색 조건에서 bfs 예상

1) bfs 

2-1) 탐색 구간이 물이고, 해당 빙하 값 0 초과이면 빙하 감소

2-2) 탐색 구간 빙하이고, 방문한 적 없으면 queue 삽입

3) bfs 호출이 2번 이상이면 종료

4) 빙하 탐색 완료 -> 해 증가

5) 빙하를 한번도 탐색하지 않으면(빙하가 없음) -> 0 출력 종료

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

/*
* 빙하 해당 좌표 벡터 삽입
* 벡터 순회
* 상, 하, 좌, 우 물 확인
* 0이 아니라면 감소
* 
* bfs
* 맵 순회
* 0이 아니면 bfs
* bfs 2회 이상이면 정답 종료
* 다 녹았다. 0 출력 종료
*/

int v[300][300];

bool bCheck[300][300];

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int n, m;

int year, t;

void clear()
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			bCheck[i][j] = false;
		}
	}
}

void bfs(int y, int x)
{
	++t;
	queue<pair<int, int>> que;
	que.push({ y,x });

	bCheck[y][x] = true;

	while (!que.empty())
	{
		int _y = que.front().first;
		int _x = que.front().second;

		que.pop();

		for (int i = 0; i < 4; ++i)
		{
			int __y = _y + dy[i];
			int __x = _x + dx[i];

			if (bCheck[__y][__x])
				continue;

			if (0 > __y || __y >= n || 0 > __x || __x >= m)
				continue;

			//다른 빙산인 경우
			if (0 < v[__y][__x])
			{
				bCheck[__y][__x] = true;
				que.push({ __y, __x });
			}

			
			//물인 경우
			if (0 == v[__y][__x] && 0 < v[_y][_x])
			{
				--v[_y][_x];
			}
		}
	}
}
int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> v[i][j];
		}
	}
	bool bRun = false;
	while (true)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (0 != v[i][j] && !bCheck[i][j])
				{
					bRun = true;
					bfs(i, j);
					if (t > 1)
					{
						cout << year << endl;
						exit(0);
					}
				}
			}
		}

		if (!bRun)
		{
			cout << 0 << endl;
			exit(0);
		}
		bRun = false;
		clear();
		t = 0;
		++year;
	}

	return 0;
}