문제

문제 링크

해설

• 인구 이동을 하려면 어떤 정보들이 필요할까요?
  • 국경을 개방한 국가의 좌표가 필요합니다.
  • 그래야 좌표들을 토대로 인구의 합과 평균을 구할 수 있기 때문입니다.
• 따라서, 임의의 좌표 (y, x)에서 DFS를 수행할 때, 국경을 개방할 조건 (L <= 인구 차이 <= R)을 만족한다면 재귀를 수행함과 동시에 외부 저장소에 좌표를 따로 저장합니다.
• 이렇게 DFS를 1회 수행하면, 임의의 좌표 (y, x)를 기준으로 국경을 개방할 수 있는 ‘연합’이 만들어집니다. 저희는 ‘연합’의 좌표를 모두 저장해놨기 때문에 순회하며 인구수 합을 구하고 평균으로 값을 갱신할 수 있습니다.
• 프로그램의 종료조건은 무엇일까요? 더 이상 인구 이동이 일어나지 않을 때 일 것입니다.
• 모든 점에 대해 DFS를 수행했을 때 연합이 단 하나도 만들어지지 않았다면? 루프문을 빠져나옵니다.

코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int N, L, R;
int land[50][50];
bool visited[50][50];
vector<pair<int, int>> pos;

int DFS(int y, int x) {
	visited[y][x] = true;
	pos.emplace_back(y, x);
	int ret = land[y][x];
	for (auto i : d) {
		int ny = y + i[0], nx = x + i[1];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx]) continue;
		int diff = abs(land[y][x] - land[ny][nx]);
		if (L <= diff && diff <= R) ret += DFS(ny, nx);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> L >> R;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			cin >> land[y][x];

	int answer = 0;
	while (true) {
		int sum;
		bool is_moved = false;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (visited[y][x]) continue;
				pos.clear();
				sum = DFS(y, x);
				if (pos.size() == 1) continue;
				for (const auto& i : pos)
					land[i.first][i.second] = sum / pos.size();
				is_moved = true;
			}
		}
		if (!is_moved) break;
		answer++;
		memset(visited, false, sizeof(visited));
	}
	cout << answer << '\n';
	return 0;
}

소스코드 링크

결과