풀이

1. 연합은 바이러스처럼 퍼져나가므로 BFS를 사용하는것이 편하다.
   (큐에 넣고 빼면서 인접한 나라들을 넣으면 됨)

2. 연합이 발생하지 않을 때 까지 반복 = while문 을 통해 무한반복 시킴.
   (while 안에 처리해주는 함수를 넣는다고 단순하게 생각)

3. Map을 for문을 돌면서 방문 했던 곳인지 검사한다. (방문했던 곳은 어짜피 인접 국가들이 겹치게 됨) 이 방문처리를 bfs 돌면서 해준다.

4. 연합 국가들을 담을 큐와 벡터를 지정한다
   큐 : front에서 부터 값을 받아서 연합 국가를 선별하고 큐에 넣은 후 front를 pop 하기 위함
   벡터 : 큐에서 빠진 국가들을 기록해둬야 어느 국가들이 연합에 있었는지 확인 가능

코드

#include <bits/stdc++.h>

using namespace std;

int n, l, r;

int Map[51][51] = { 0, };
int visited[51][51] = { 0, };

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

int sum = 0;
int day = 0;
int flag = 1;

queue<pair<int, int>> trade;
vector<pair<int, int>> area;

void bfs(int x, int y)
{
	// 처음에 들어온 값을 넣어준다.
	trade.push(area[0]);
	visited[x][y] = 1;

	while (!trade.empty())
	{
		// q에 들어온 값은 빼면서 합계에 넣어줌.
		pair<int, int> temp = trade.front();
		sum += Map[temp.first][temp.second];
		trade.pop();

		for (int t = 0; t < 4; t++)
		{
			int cx = temp.first;
			int cy = temp.second;

			int nx = temp.first + dx[t];
			int ny = temp.second + dy[t];

			if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] == 1)
				continue;
			else
			{
				int dif = abs(Map[cx][cy] - Map[nx][ny]);
				// 두 도시의 인구수 차이가 L이상 R이하면
				if (dif >= l && dif <= r)
				{
					visited[nx][ny] = 1;
					area.push_back(make_pair(nx, ny));
					trade.push(make_pair(nx, ny));
				}
			}
		}
	}
}

int main()
{
	cin >> n >> l >> r;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> Map[i][j];
		}
	}

	while (flag)
	{
		flag = 0;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				visited[i][j] = 0;
		}

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (!visited[i][j])
				{
					area.clear();
					sum = 0;
					area.push_back(make_pair(i, j));
					bfs(i, j);

					// 연합이 생겼다는 뜻이므로 평균 값 넣어주고 day++
					if (area.size() >= 2)
					{
						flag = 1;
						for (int t = 0; t < area.size(); t++)
						{
							Map[area[t].first][area[t].second] = sum / area.size();
						}
					}
				}

			}
		}

		if (flag == 1)
			day++;
	}

	cout << day;

	return 0;
}

후기

이전에 푼 플래5 큐빙 문제를 풀고 이걸 푸니 매우 기분이 좋다.
큐빙은 어려운건 없었는데 머리 속에서 큐브를 3차원으로 돌려가면서 푸니까 그래픽 카드가 딸려서 그런지 발열이 심해져서 실제 큐브를 갖다놓고 풀었다.

과정이 조금 복잡하기 때문에 골드5 문제는 아닌것 같다.