[백준 16234] 인구이동

문제요약

2차원 배열 상에서 인구이동이 몇 번 이루어질 수 있는지 시뮬레이션 하세요.
각 배열 칸은 나라이며, 상하좌우로 인접한 칸들은 국경선을 공유하는 나라입니다.
참고로 인구 이동은 오늘부터 시작하고, 인구 이동이 없어질 때까지 진행하면 됩니다.

인구이동 1회 당...

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

인풋

• N : 대륙의 크기(1 ≤ N ≤ 50). 대륙은 N*N크기의 배열로 이루어져있다.
• L,R : 국경선을 열지 결정하는 데 참고할 상수
• 2차원 배열(N*N) : 각 칸 별 사람 수

단, 인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

아웃풋

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

아이디어

그냥 정확한 시뮬레이션

헷갈렸던 점

문제 상에선 열 수 있는 국경선을 모두 열어두고 연합 별 평준화 작업을 하라고 한다.
이 말만 보고
1. 열 수 있는 모든 국경선 열고 저장하기
2. 1번에서 정리 해둔 것을 참고하며 BFS하면서 component 저장
3. 2번에서 얻은 연합들에 대해 평준화 작업
이렇게 하려고 계획했었다.

근데 1번 2번을 나누는 게 큰 의미가 없다. 왜냐하면 2번을 할 때 bfs가 끝나자 마자 인구 수를 수정하는 게 아니고, bfs가 모든 seed(pivot)에 대해 끝났을 때 인구 수를 수정하기 때문이다.
그래서 1번을 없애고, 2번에서 BFS를 할 때 adjacent 조건(같은 component로 취급할 수 있는 조건)에서 L과 R을 활용한 조건으로 적용했다.

삽질

시간초과 : seed 구하기

모든 seed에 대해 component를 매 시뮬레이션 단계(level)마다 구한다.

나의 경우 seed(코드 상 pivot)을 구하는 부분을 2차원 배열을 처음부터 끝까지 순회하는 방법으로 구현했다. 이렇게 했을 때 seed를 바꿀 때(level이 바뀐 건 아니다) 이미 검사한 2차원 배열의 윗부분을 다시 검사해주는 문제가 생긴다. 그래서 같은 시뮬레이션 레벨이면 이전 seed 다음부분부터 검사하는 방법으로 개선을 해서 통과할 수 있었다.

반면 모든 component를 구하는 bfs는 크게 문제가 되지 않는다. 어차피 모든 vertice를 방문하는 거니까.... bfs의 O(vertice 개수+E) = O(vertice 개수+4vertice 개수)일 것이다.(E는 각 vertice마다 4개의 인접 vertice를 검사하기 때문)
vertive 개수가 최대 100*100이긴한데... 배열이라 빠르게 동작하는 거 같다.

소스코드

#include<iostream>
#include<math.h>
#include<queue>
#include<memory.h>
using namespace std;
int tab[100][100];
int former[100][100];
int visited[100][100];
int n, l, r;
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
struct pos {
	int i, j;
};
bool inbox(int i, int j) {
	return i >= 0 && i < n&& j >= 0 && j < n;
}

pos pick_piv() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] == 0) {//0명인 국가도 가능
				return pos{ i,j };
			}
		}
	}
	return pos{ -1, -1 };
}
void init_visited() {
	memset(visited, 0, sizeof(visited));
}

void bfs(int ctr, pos piv) {
	queue<pos> q;
	q.push(piv);
	visited[piv.i][piv.j] = ctr;
	//print_visited();
	while (!q.empty()) {
		pos cur = q.front();
		q.pop();

		for (int k = 0; k < 4; k++) {
			int ci = cur.i + di[k], cj = cur.j + dj[k];
			if (inbox(ci, cj)) {//0명인 국가도 가능
				int s = abs(tab[cur.i][cur.j] - tab[ci][cj]);
				if (s >= l && s <= r && visited[ci][cj] == 0) {
					q.push(pos{ ci, cj });
					visited[ci][cj] = ctr;
				}
			}
		}
		//print_visited();
	}
}
bool issame() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (former[i][j] != tab[i][j]) {
				return false;
			}
		}
	}
	return true;
}

void med_tab() {
	int sum_idx[100 * 100];
	int reg_idx[100 * 100];
	memset(sum_idx, 0, sizeof(sum_idx));
	memset(reg_idx, 0, sizeof(reg_idx));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum_idx[visited[i][j]] += tab[i][j];
			reg_idx[visited[i][j]]++;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int med_val = sum_idx[visited[i][j]] / reg_idx[visited[i][j]];//소숫점 버림
			tab[i][j] = med_val;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	cin >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tab[i][j];
		}
	}
	//시뮬
	int level = 0;
	for (; level <= 2000; level++) {
		memcpy(&former[0][0], &tab[0][0], sizeof(tab));
		init_visited();
		pos piv = pick_piv();
		int ctr = 1;
		//현재 인구수 기준으로 bfs 컴포넌트 구해둠
		while (piv.i != -1) {
			//cout <<"level : "<<level<<" , ctr : "<<ctr<< " ,  pivot : " << piv.i << " " << piv.j << endl;
			bfs(ctr, piv);
			ctr++;
			piv = pick_piv();
		}
		med_tab();
		//print_tab();
		if (issame()) {
			break;
		}
	}
	cout << level;
}