2636번: 치즈 - 그래프(BFS)

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

2636번: 치즈

 

0. 주어진 판의 왼쪽 끝은 치즈가 없음이 보장되므로, 그 좌표를 시작점으로 정해 bfs 탐색을 진행한다.

1. 지금껏 방문하지 않은 좌표들로 bfs 탐색을 진행하는데, 이때

1-1. 방문한 좌표가 치즈라면, 치즈 좌표를 담은 queue(quCheese)에 따로 저장한다.

1-2. 방문한 좌표가 치즈가 아니라면, 평범하게 탐색에 진행할 때 쓰는 queue(quVis)에 저장한다.

2. quVis가 empty가 될 때까지 탐색을 진행한다. 탐색이 끝났다는 것은 현 상태에서 공기에 접촉한 치즈 좌표를 전부 저장했다는 뜻이다.

3. 공기에 접촉한 치즈 좌표가 없다면 답을 출력한다. 그렇지 않다면 quVis와 quCheese를 swap해 1~2과정을 반복한다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int R, C;
bool board[101][101];
bool vis[101][101];
int dir[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}};

queue<pii> quVis, quCheese;
int meltTime{0}, leftCheese;

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

	cin >> R >> C;
	for (int i{1}; i <= R; i++)
	{
		for (int j{1}; j <= C; j++)
		{
			cin >> board[i][j];
		}
	}

	quVis.push({1, 1});
	vis[1][1] = true;

	while (true)
	{
		while (!quVis.empty())
		{
			auto [X, Y] = quVis.front();
			quVis.pop();

			for (int i{0}; i < 4; i++)
			{
				int x = X + dir[0][i], y = Y + dir[1][i];
				if (x >= 1 && x <= R && y >= 1 && y <= C)
				{
					if (vis[x][y])
						continue;

					if (board[x][y])
						quCheese.push({x, y});
					else
						quVis.push({x, y});

					vis[x][y] = true;
				}
			}
		}

		if (quCheese.empty())
		{
			cout << meltTime << "\n"
				 << leftCheese << "\n";
			break;
		}

		meltTime++;
		leftCheese = quCheese.size();
		quVis.swap(quCheese);
	}
}