알고리즘 :: 백준 :: 16234 - 인구 이동

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 땅 크기 N×N (1 ≤ N ≤ 50)
• L ≤ 인구 차이 ≤ R (1 ≤ L ≤ R ≤ 100)

✏️ 문제풀이

문제에 인구 이동 로직이 나와있기 때문에 그대로 실수없이 구현하면 되는 문제입니다.
인구 이동 과정은 ① 연합 만들기 - ② 인구 이동 - ③ 인구 이동 ? 시간 증가 : 종료 후 정답 출력으로 요약할 수 있습니다. 코드로 간략하게 나타내면 다음과 같습니다.

while (true) {
	// 1. 연합 만들기
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            if (visited[y][x]) continue;
            sum = 0;
            dfs(y, x);
            // 2-1. 연합이 안 만들어졌다? 다른 칸 검사
            if (unite.size() == 1) {					
                unite.pop_back();
                continue;
            }
            // 2-2. 연합이 만들어졌다면, 인구 이동
            startMove();
            moveFlag = true;
        }
    }
    // 3. 인구 이동 여부에 따라 시간증가 or 프로그램 종료
    if (!moveFlag) break;
    ans++;
}

 

연합은 임의의 시작점을 기점으로 DFS를 1회 돌리면 만들 수 있습니다.
갈 수 있는 모든 국가에 방문표시 및 외부 배열에 좌표를 저장합니다.

 

이렇게 연합이 만들어지면, 인구 이동을 실시합니다.

 

모든 점을 검사했는데, 인구 이동이 발생하지 않았다면 정답을 출력합니다.

📝 코드

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

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

int N, L, R, sum;
bool visited[101][101];
array<array<int, 101>, 101> arr;
vector<pair<int, int>> unite;

void dfs(int y, int x) {
	visited[y][x] = true;
	unite.push_back({y, x});
    sum += arr[y][x];
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i], nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx]) continue;
		
		int diff = abs(arr[ny][nx] - arr[y][x]);
		if (L <= diff && diff <= R)	dfs(ny, nx);
	}
}

void startMove() {
	int newVar = sum / unite.size();
	while (!unite.empty()) {
		int y, x; tie(y, x) = unite.back();
		arr[y][x] = newVar;
		unite.pop_back();
	}
}
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 >> arr[y][x];
	
    unite.reserve(N * N);
    
	int ans = 0;
	while (true) {
        bool moveFlag = false;
		memset(visited, false, sizeof(visited));
		for (int y = 0; y < N; ++y) {
			for (int x = 0; x < N; ++x) {
				if (visited[y][x]) continue;
                sum = 0;
				dfs(y, x);
				if (unite.size() == 1) {					
                    unite.pop_back();
					continue;
				}
				startMove();
				moveFlag = true;
			}
		}
        if (!moveFlag) break;
		ans++;
	}
	cout << ans;
}

 

🔗 코드 링크

🕧 결과