[백준 16234] 인구 이동 - C언어(C++)

 

 

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

16234번: 인구 이동

 문제 설명

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

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

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

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

 

 

---

이런 문제 좋아하는 편 ㅎㅎ

문제처럼 어떤 조건이 허락되면? => A를 확인하고 => A과 확인되면 => B의 작업을 수행한다. 와 같은 차례가 진행된다면 정말 논리 그대로 하나하나 확인해보고 조건에 맞으면 작업을 수행하면 된다. 

 

큰 숲부터 주요 로직들만 확인해보자.

void solution() {
	int date = 0;
	while (1) {
		if (movedPopulation()) date++;
		else break;
		closeLines();
	}
	cout << date;
}

인구가 이동되었다면? 날짜를 세주지만, 더이상 이동되지 않는다면 반복문을 멈추었고 날짜 출력후 마무리하였다.

 

 

int movedPopulation() {
	// 조건에 맞는 국경선이 열리면 인구 이동
	int flag = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!opened[i][j]) {
				int countryCnt = openLines(i, j);
				if (countryCnt != 1) {
					v.push_back({ i,j });
					int population = int(total_population / countryCnt);
					movePopulation(population);
					flag = 1;
				}
			}
		}
	}
	return flag;
}

인구 이동은 다음과 같다. 여기엔 또 국경선이 열리지 않은 곳이 있다면(!opened[i][j]) 주변에 국경선을 열 수 있는 곳이 있는지 찾아보고(openLines 함수)  국경선을 열었다면, 한 영역별 인구수를 찾고 인구를 나누어 이동시켰다(movePopulation 함수)  그리고 인구 이동이 한 번 이상 일어났음을 뜻하기 위해 flag는 1의 값을 갖는다.

 

 

 

int openLines(int y, int x) {
	total_population = map[y][x];
	int countryCnt = 1;

	q.push({ y,x });
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
			if (!opened[ny][nx] && l <= abs(map[y][x]-map[ny][nx]) && abs(map[y][x] - map[ny][nx]) <= r) {
				q.push({ ny,nx });
				v.push_back({ ny,nx });
				opened[y][x] = true;
				opened[ny][nx] = true;
				total_population += map[ny][nx];
				countryCnt++;
			}
		}
	}
	return countryCnt;
}

이것이 openLines함수. bfs 알고리즘이며, bfs가 가능한 자리에 국경선이 열림을 표시하였으며(opened[ny][nx]=true), 전체 인구의 수와 국경선이 열리는 국가의 수를 세주었다. vector에 위치좌표를 넣음으로써 국경선이 열린 국가들을 기억했다.

 

 

void movePopulation(int population) {
	while (!v.empty()) {
		int y = v.back().first;
		int x = v.back().second;
		v.pop_back();
		map[y][x] = population;
	}
}

movePopulation 함수로, 벡터 내에 있는 좌표값의 지도에 나누어진 인구수로 재정의하였다.

 

 

 

 

<< 전체 코드 >>

#include <iostream>
#include <cstdbool>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

int map[50][50];
bool opened[50][50];
queue<pair<int, int>> q;
vector<pair<int, int>> v;
int total_population = 0;
int n, l, r;

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

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

int openLines(int y, int x) {
	total_population = map[y][x];
	int countryCnt = 1;

	q.push({ y,x });
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
			if (!opened[ny][nx] && l <= abs(map[y][x]-map[ny][nx]) && abs(map[y][x] - map[ny][nx]) <= r) {
				q.push({ ny,nx });
				v.push_back({ ny,nx });
				opened[y][x] = true;
				opened[ny][nx] = true;
				total_population += map[ny][nx];
				countryCnt++;
			}
		}
	}
	return countryCnt;
}

void movePopulation(int population) {
	while (!v.empty()) {
		int y = v.back().first;
		int x = v.back().second;
		v.pop_back();
		map[y][x] = population;
	}
}

int movedPopulation() {
	// 조건에 맞는 국경선이 열리면 인구 이동
	int flag = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!opened[i][j]) {
				int countryCnt = openLines(i, j);
				if (countryCnt != 1) {
					v.push_back({ i,j });
					int population = int(total_population / countryCnt);
					movePopulation(population);
					flag = 1;
				}
			}
		}
	}
	return flag;
}

void closeLines() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			opened[i][j] = false;
}

void solution() {
	int date = 0;
	while (1) {
		if (movedPopulation()) date++;
		else break;
		closeLines();
	}
	cout << date;
}

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

	input();
	solution();
	return 0;
}

 

Point
- BFS 알고리즘
- opened 2차원 배열을 통해 연맹가능한 국가 찾기
- 연맹가능한 국가는 vector에 넣기