백준 16234번 - 인구 이동 (2회 차)

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

16234번: 인구 이동

풀이 과정

 인구 차가 주어진 범위 내에 있는 국가들은 연결되고 연결된 국가들의 값이 연결된 국가들의 인구의 평균으로 바뀌고 하루가 지난다. 몇 일이 지나야 인구 이동이 끝나는지를 구하는 문제이다.

 

 하루에 한번  모든 그래프의 인구 이동과 평균을 해주기 위해서 while문에서 매번 day를 더해주고 visited를 초기화 해준다. 

 

 매일 모든 나라를 방문하며 연결 컴포넌트를 구한다. 연결 컴포넌트를 구할 때 범위 내에 있어야 한다는 조건을 추가한다. 한 연결 컴포넌트를 순회하면서 union_list에 좌표를 기록한다. 방문이 끝나면 연결 컴포넌트의 평균을 구하고 union_list 좌표가 가르키는 값에 평균값을 대입한다. 이때 값이 다르다면 변화가 있었던 것으로 changed_flag를 true로 바꿔준다.

 

 이후 변화가 없을 때 changed_flag가 false가 되며 while문을 탈출한다. 마지막 변화가 없는 날 하루를 더 관찰했으므로 day에서 하루를 빼고 출력한다.

 

느낀 점

 매번 바뀌는 연결 컴포넌트 구조를 만들며 몇 번까지 바뀌는지 구하는 문제였다. 시뮬레이션 문제는 큰 틀을 잡고 안에 세세한 조건을 잘 추가해주는 것이 중요한 것 같다.

 

 

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

const int MAX = 54;
int visited[MAX][MAX], mp[MAX][MAX];
int n, bot, top, sum, cnt, day;
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> union_list;
bool changed_flag = true;

//기록된 노드 평균으로 채우기
void fill_avg(int fill) {
	for (int i = 0; i < union_list.size(); i++) {
		int y = union_list[i].first;
		int x = union_list[i].second;
		if(mp[y][x] != fill) changed_flag = true;
		mp[y][x] = fill;
	}
	return;
}

//탐색 하며 노드 기록
void DFS(int y, int x) {
	union_list.push_back({ y, x });
	sum += mp[y][x];
	visited[y][x] = 1;
	for (int d = 0; d < 4; d++) {
		int ny = my[d] + y;
		int nx = mx[d] + x;
		if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
		//인구 차이 조건
		int gab = abs(mp[y][x] - mp[ny][nx]);
		if (gab < bot || gab > top) continue;
		DFS(ny, nx);
	}
	cnt++;
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//입력
	cin >> n >> bot >> top;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mp[i][j];
		}
	}

	//멈출 때 까지 반복
	do {
		changed_flag = false; day++;
		fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j]) continue;
				sum = 0; cnt = 0; union_list.clear();
				DFS(i, j);
				fill_avg(sum / cnt);
			}
		}
		/* 테스트 출력
		cout << "인구 이동 후 \n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << mp[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";
		*/
	} while (changed_flag);

	cout << day - 1;

	return 0;
}