(c++)백준 16234번: 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

[풀이]

문제에 있는 규칙대로 구현하면 되는 문제였다.

구현 순서

1. 국경선 열기

2. 인구 이동

3. 연합 해체, 국경선 닫기

 

1. 국경선 열기

- vector<Country>Union[1250]을 선언하여 사용하였다. (County 구조체는 나라의 위치와 인구수 포함, 1250은 50*50배열에서 나올 수 있는 최대 연합의 수)

- dfs를 이용해서 서로 인접한 나라의 인구 수 차이가 L이상 R이하인 경우 연합을 저장하는 벡터에 넣어줬다. bool check[50][50]을 확인한 나라를 표시하는 데 사용

- 연합 개수 카운트

 

2. 인구 이동

- 연합마다 인구 계산해서 각 나라 인구수 갱신

 

3. 연합 해체, 국경선 닫기

- Union 벡터 clear

- 연합 개수 0으로 초기화

- check 배열 false로 초기화

 

 

#include <iostream>
#include <vector>
#include <cstring>//memset
#include <cstdlib>//abs
using namespace std;

struct Country {
	int x, y;
	int p;//인구 수
};

int N, L, R;
int A[50][50];
int unionCnt;
bool flag = false;
bool check[50][50];//해당 나라가 연합에 포함되어 있는지
const int dx[] = { -1,1,0,0 };//위, 아래
const int dy[] = { 0,0,-1,1 };//왼, 오
vector<Country>Union[1250];//같은 연합에 포함된 나라들 저장 인구수 조정에 사용
//연합은 50*50에서 최대 1250개 나올 수 있음!

void init() {
	memset(check, false, sizeof(check));
	for (int i = 0; i < unionCnt; i++) {
		Union[i].clear();
	}
	unionCnt = 0;
}

void dfs(int x, int y, int u_n) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N || check[nx][ny])
			continue;
		int d = abs(A[x][y] - A[nx][ny]);
		if (d >= L && d <= R) {
			check[nx][ny] = true;
			Union[u_n].push_back({ nx,ny,A[nx][ny] });
			dfs(nx, ny, u_n);
		}
	}
}

void getUnion() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//아직 연합에 속하는지 확인 안 한 나라면
			if (check[i][j] == false) {
				check[i][j] = true;
				dfs(i, j, unionCnt);
				if (!Union[unionCnt].empty()) {
					Union[unionCnt].push_back({ i,j,A[i][j] });
					unionCnt++;
				}
			}
		}
	}
}

void Move() {
	//연합마다 인구 이동
	for (int i = 0; i < unionCnt; i++) {
		//연합 내 전체 인구수
		int All = 0;
		int unionSize = Union[i].size();
		for (int j = 0; j < unionSize; j++) {
			All += Union[i][j].p;
		}
		int np = All / unionSize;
		for (int j = 0; j < unionSize; j++) {
			int x = Union[i][j].x;
			int y = Union[i][j].y;
			A[x][y] = np;
		}
	}
}

void solution() {
	cin >> N >> L >> R;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> A[i][j];
		}
	}
	while (1) {
		init();
		//연합 구하기, 연합 없으면 끝
		getUnion();
		if (unionCnt>0) {
			Move();
			ans++;
		}
		else
			break;
		/*for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << A[i][j] << ' ';
			}
			cout<<'\n';
		}*/
	}
	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}

 

※bfs로 푼 코드

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>//memset
#include <cmath>//abs
using namespace std;

struct Pos {
	int x, y;
};

int N, L, R;
int A[50][50];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
bool check[50][50];
vector<Pos>Union;

void bfs(int startx, int starty) {
	Union.push_back({ startx,starty });
	queue<Pos>q;
	q.push({ startx,starty });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			//국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하면
			if (abs(A[x][y] - A[nx][ny]) >= L && abs(A[x][y] - A[nx][ny]) <= R && check[nx][ny] == false) {
				check[nx][ny] = true;
				Union.push_back({ nx,ny });
				q.push({ nx,ny });
			}
		}
	}
}

int getUnion() {
	int t = 0;
	while (1) {
		memset(check, false, sizeof(check));
		bool flag = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (check[i][j] == true)
					continue;
				check[i][j] = true;
				bfs(i, j);
				//연합이 생겼으면
				if (Union.size() > 1) {
					int p_cnt = 0;
					flag = true;
					int Union_cnt = Union.size();
					for (int u = 0; u < Union_cnt; u++) {
						int x = Union[u].x;
						int y = Union[u].y;
						//연합의 인구수 세기
						p_cnt += A[x][y];
					}
					int np_cnt = p_cnt / Union_cnt;
					for (int u = 0; u < Union_cnt; u++) {
						int x = Union[u].x;
						int y = Union[u].y;
						A[x][y] = np_cnt;
					}
				}
				Union.clear();
			}
		}
		if (flag == false)
			break;
		else t++;
	}
	return t;
}

int main() {
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> A[i][j];
		}
	}
	cout << getUnion() << '\n';
	return 0;
}