[G4] 백준 16234번 인구 이동 C++ 구현, 시뮬레이션, BFS

리뷰

 

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

모든 나라의 인구 차이가 L이상 R이하 범위 일때까지 인구를 이동시키는 문제

뇌 빼고 구현하긴 했는데 시간이 꽤 많이 걸려서 아마 더 최적해가 있을 듯 하다.

 

전역 변수

• n : 땅의 한 변의 길이를 저장할 변수
• l, r : 각 나라당 인구 차이의 범위를 저장할 변수
• idx : 각 나라를 그룹으로 묶을때 사용할 변수
• ans : 몇일간 인구 이동이 진행되는지를 저장할 변수
• lst : 각 나라의 인구 수를 저장하기 위한 정수형 배열, 최대 50 * 50크기
• v : 각 나라가 속한 그룹을 저장하기 위한 정수형 배열, 최대 50 * 50크기
• dx, dy : 4방향 탐색을 진행할 방향 배열
• Pos : 시뮬레이션 시 현재 x, y좌표를 저장하기 위한 구조체
• VC : 그룹의 인구의 총 합과 나라의 수를 저장하기 위한 구조체
• vcs : 각 그룹 별 총 인구 및 나라의 수를 저장하기 위한 VC타입 배열, 최대 2500크기

 

함수

1. bfs

void bfs(int sx, int sy, int idx)

 

인구 이동을 시뮬레이션 하기 위한 너비 우선 탐색 함수

1. 매개변수로 시작 지점의 좌표 sx, sy와 그룹 정보 idx를 입력 받는다.
2. Pos타입의 q를 초기화 하고, sx, sy를 push해준다.
3. v 배열의 sx, sy인덱스에 그룹 정보 idx를 기록해 준다.
4. vcs의 idx의 val에 현재 위치의 인구 수를 더해주고, cnt를 증가시킨다.
5. q가 빌때까지 반복문을 수행해 주고, 현재 큐의 맨 앞에 있는 요소를 가져와 준다.
6. 4방향을 탐색하며 범위 내이고, 방문하지 않았으며 두 나라의 인구 차가 l이상 r이하일 경우 이동을 진행한다.
7. 해당 나라를 idx그룹으로 묶어주고, 속한 그룹의 인구수와 나라 수를 증가시켜준다.
8. 큐에 이동한 나라의 좌표를 추가해 준다.

 

2. input

void input()

 

요소를 입력받기 위한 함수

1. n, l, r을 입력 받고주고, n * n크기의 각 나라당 인구수를 입력 받아준다.

 

3. init

void init()

 

하루가 바뀔 때마다 사용한 변수 및 배열을 초기화 하기 위한 함수

1. idx를 1로, v와 vcs배열을 초기화 해준다.

 

4. solution

void solution()

 

인구 이동 시뮬레이션 후 실제로 인구 이동을 진행해 주는 함수

1. 각 나라를 순회하며 아직 그룹에 속해있지 않은 나라를 방문한 bfs함수를 진행해 준다.
2. 이때 매개변수로는 해당 나라의 x, y좌표와 idx를 전달하고, idx를 증가시켜 주어야 한다.
3. 모든 bfs작업을 통해 시뮬레이션을 진행한 데이터를 갖고 실제 나라의 인구를 이동시켜 준다.
4. 각 나라를 순회하며 나라의 인구를 자신이 속한 그룹의 인구 총합 / 나라의 수로 변경시켜 준다.

 

// 5. print

//void print()

 

디버깅용 함수

1. 시뮬레이션이 진행된 각 일자마다 인구의 이동과 각 나라가 속한 그룹을 출력해준다.

 

문제풀이

1. input함수를 통해 문제 풀이에 필요한 변수와 배열 정보를 입력 받아준다.
2. 무한히 반복하는 while문을 실행해 준다.
3. init함수를 통해 각 일자에 필요한 변수와 배열을 초기화 해준다.
4. solution함수를 통해 시뮬레이션 및 인구 이동이 완료된 결과를 반영해 준다.
5. 만약 idx가 모든 나라의 수보다 1이 크다면 더 이상 그룹이 없는 상태이므로 break 처리해 준다.
6. 아니라면 ans를 증가시켜 준다.
7. while문이 종료된 후에 ans에 저장된 값을 출력해 준다.

 

참고 사항

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

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

 

정답 코드

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

int n, l, r, idx, ans;
int lst[50][50];
int v[50][50];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y;
};

struct VC {
	int val, cnt;
};

VC vcs[2500];

void bfs(int sx, int sy, int idx) {
	queue<Pos> q;
	q.push({ sx, sy });
	v[sx][sy] = idx;
	vcs[idx].val += lst[sx][sy];
	vcs[idx].cnt++;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;
		
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !v[nx][ny] && l <= abs(lst[cx][cy] - lst[nx][ny]) && abs(lst[cx][cy] - lst[nx][ny]) <= r) {
				v[nx][ny] = idx;
				vcs[idx].val += lst[nx][ny];
				vcs[idx].cnt++;
				q.push({ nx, ny });
			}
		}
	}
}

void input() {
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
		}
	}
}

void init() {
	idx = 1;
	memset(v, 0, sizeof(v));
	memset(vcs, 0, sizeof(vcs));
}

void solution() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (v[i][j]) continue;
			bfs(i, j, idx++);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			VC vc = vcs[v[i][j]];
			lst[i][j] = vc.val / vc.cnt;
		}
	}
}

//void print() {
//	cout << "\n";
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < n; j++) {
//			cout << lst[i][j] << " ";
//		}
//		cout << "\n";
//	}
//	
//	cout << "\n";
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < n; j++) {
//			cout << v[i][j] << " ";
//		}
//		cout << "\n";
//	}
//}

int main() {
	input();

	while (1) {
		init();
		solution();
		//print();

		if (idx == n * n + 1) break;
		else ans++;
	}
	cout << ans;
}