[BOJ][백준 16234] 인구 이동 - C++

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

16234번: 인구 이동

백준 사이트의 16234번 문제, 인구 이동 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

나라 간에 인구 이동이 일어나는 모습

• N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다.
• 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다.
• 인접한 나라 사이에는 국경선이 존재한다.
• 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
  • 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
  • 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
  • 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
  • 연합을 해체하고, 모든 국경선을 닫는다.

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

---

1. 문제풀이 아이디어

• 소속, 연맹이라 혹시 union / find를 사용해야 하나했지만 전형적인 BFS알고리즘 문제였다.
• BFS의 시작지점은 아직 소속이 없는 국가를 찾는 순간 그 지점에서 시작하면 된다.
• BFS로 주변 국가로 이동이 가능한지 체크하고 같은 연맹끼리 마킹해준다.
• 이동 가능한 국가 파악이 끝나면 인구이동을 시작해준다.

---

2. 코드 핵심 부분

1) 알고리즘의 총 단계를 품고 있는 solve 함수,

   아마 여기서 시간이 좀 걸린것 같은데 최적화가 필요할 것 같다.

// 문제풀이 함수
void solve() {

	while (1) {
		int flag = 0;
		// 초기화
		memset(Map, 0, sizeof(Map));
		memcpy(cPeople, People, sizeof(People));
		Marker = 1;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Map[i][j])
					continue;

				int ret = 0;
				// 필요한 변수 초기화
				nowPeople = 0;
				nowCnt = 0;

				// BFS탐색 해주고 인구 이동 있으면 1, 없으면 0 받음
				ret = bfs(i, j);
				flag += ret;

				// 인구이동 있으면 인구수 이동 함수 실행하고 마커 변경해줌
				// 근데 이러면 인구이동하고 다음 연합을 체크하게 됨.
				// 원본 인구수를 남기기로 함.
				if (ret == 1) {
					changePeo();
					Marker++;
				}
			}
		}

		// 인구 이동 없었으면 끝
		if (flag == 0)
			return;

		// 인구수 이동 있었으면 날짜 +1
		memcpy(People, cPeople, sizeof(People));
		Ans++;
	}
}

 

2) 이 국가에서 인구 이동이 가능한지 체크하는 BFS 함수,

   기본적인 BFS 틀인데 가능성 판별을 위해 처음 국가를 분리하느라 코드가 쓸데없이 길어졌다.

   인구 이동이 가능한지 체크하는 것을 다른 방법으로 구현한다면 코드 길이도 짧아지고

   실행시간도 단축시킬 수 있을 것으로 예상된다.

// 인구 이동이 있는지 체크해주는 BFS 함수
int bfs(int Sy, int Sx) {

	queue<Node> q;
	q.push({ Sy, Sx });

	int flag = 0;
	int visited[50][50] = { 0 };
	visited[Sy][Sx] = 1;

	int Diry[4] = { -1, 0, 1, 0 };
	int Dirx[4] = { 0, -1, 0, 1 };

	// 처음은 따로 체크 (가능성 판별 위해)
	Node Now = q.front();
	q.pop();
	nowPeople += People[Now.y][Now.x];
	nowCnt++;

	for (int i = 0; i < 4; i++) {

		int Ny = Now.y + Diry[i];
		int Nx = Now.x + Dirx[i];

		if (Ny < 0 || Nx < 0 || Ny >= N || Nx >= N)
			continue;

		// 차이가 L이상 R이하 여야함
		int Diff = abs(People[Now.y][Now.x] - People[Ny][Nx]);
		if (Diff < L || Diff > R)
			continue;
		
		flag = 1;
		visited[Ny][Nx] = 1;
		q.push({ Ny, Nx });
	}

	// 만약 flag가 0이면 0 리턴
	if (flag == 0)
		return 0;

	// 이제 가능한거 확인했으니 시작
	Map[Sy][Sx] = Marker;
	while (!q.empty()) {

		Now = q.front();
		q.pop();
		nowPeople += People[Now.y][Now.x];
		nowCnt++;
		Map[Now.y][Now.x] = Marker;

		for (int i = 0; i < 4; i++) {

			int Ny = Now.y + Diry[i];
			int Nx = Now.x + Dirx[i];

			if (Ny < 0 || Nx < 0 || Ny >= N || Nx >= N)
				continue;

			if (visited[Ny][Nx] == 1)
				continue;

			// 차이가 L이상 R이하 여야함
			int Diff = abs(People[Now.y][Now.x] - People[Ny][Nx]);
			if (Diff < L || Diff > R)
				continue;

			visited[Ny][Nx] = 1;
			q.push({ Ny, Nx });
		}
	}

	return 1;
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/*
1. 문제읽기

*/

/*
2. 아이디어
BFS로 영역 표시
시작지점 어디? 지도에 0인 곳 (소속 없으면)
union/find를 생각했지만 필요없을듯.
*/

struct Node {
	int y;
	int x;
};

// 필요 인자들
int Map[50][50]; // 소속 표시하는 지도
int People[50][50]; // 각 영역의 인구 수
int cPeople[50][50]; // 복제하기 위한 배열
int N; // 지도 크기
int L, R; // L명 이상, R명 이하
int Marker = 1; // 소속 표시할 마커, 1부터 시작
int nowPeople, nowCnt; // 각 bfs 시행마다 인구수 몇인지 나라몇인지 기록
int Ans;

// 값 입력받는 함수
void input() {
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> People[i][j];
		}
	}
}

// 인구 이동 함수
void changePeo() {

	int changeN = nowPeople / nowCnt;

	// Marker와 같은 나라 찾아서 인구 변경 해준다.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (Map[i][j] == Marker)
				cPeople[i][j] = changeN;
		}
	}
}

// 인구 이동이 있는지 체크해주는 BFS 함수
int bfs(int Sy, int Sx) {

	queue<Node> q;
	q.push({ Sy, Sx });

	int flag = 0;
	int visited[50][50] = { 0 };
	visited[Sy][Sx] = 1;

	int Diry[4] = { -1, 0, 1, 0 };
	int Dirx[4] = { 0, -1, 0, 1 };

	// 처음은 따로 체크 (가능성 판별 위해)
	Node Now = q.front();
	q.pop();
	nowPeople += People[Now.y][Now.x];
	nowCnt++;

	for (int i = 0; i < 4; i++) {

		int Ny = Now.y + Diry[i];
		int Nx = Now.x + Dirx[i];

		if (Ny < 0 || Nx < 0 || Ny >= N || Nx >= N)
			continue;

		// 차이가 L이상 R이하 여야함
		int Diff = abs(People[Now.y][Now.x] - People[Ny][Nx]);
		if (Diff < L || Diff > R)
			continue;
		
		flag = 1;
		visited[Ny][Nx] = 1;
		q.push({ Ny, Nx });
	}

	// 만약 flag가 0이면 0 리턴
	if (flag == 0)
		return 0;

	// 이제 가능한거 확인했으니 시작
	Map[Sy][Sx] = Marker;
	while (!q.empty()) {

		Now = q.front();
		q.pop();
		nowPeople += People[Now.y][Now.x];
		nowCnt++;
		Map[Now.y][Now.x] = Marker;

		for (int i = 0; i < 4; i++) {

			int Ny = Now.y + Diry[i];
			int Nx = Now.x + Dirx[i];

			if (Ny < 0 || Nx < 0 || Ny >= N || Nx >= N)
				continue;

			if (visited[Ny][Nx] == 1)
				continue;

			// 차이가 L이상 R이하 여야함
			int Diff = abs(People[Now.y][Now.x] - People[Ny][Nx]);
			if (Diff < L || Diff > R)
				continue;

			visited[Ny][Nx] = 1;
			q.push({ Ny, Nx });
		}
	}

	return 1;
}

// 문제풀이 함수
void solve() {

	while (1) {
		int flag = 0;
		// 초기화
		memset(Map, 0, sizeof(Map));
		memcpy(cPeople, People, sizeof(People));
		Marker = 1;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Map[i][j])
					continue;

				int ret = 0;
				// 필요한 변수 초기화
				nowPeople = 0;
				nowCnt = 0;

				// BFS탐색 해주고 인구 이동 있으면 1, 없으면 0 받음
				ret = bfs(i, j);
				flag += ret;

				// 인구이동 있으면 인구수 이동 함수 실행하고 마커 변경해줌
				// 근데 이러면 인구이동하고 다음 연합을 체크하게 됨.
				// 원본 인구수를 남기기로 함.
				if (ret == 1) {
					changePeo();
					Marker++;
				}
			}
		}

		// 인구 이동 없었으면 끝
		if (flag == 0)
			return;

		// 인구수 이동 있었으면 날짜 +1
		memcpy(People, cPeople, sizeof(People));
		Ans++;
	}
}

// 메인함수
int main() {

	// input
	input();

	// solve -> 만약 Map이 0이라면 BFS 탐색 시작
	//       -> 전부 탐색했는데 이동 전부 불가능하다면 끝
	solve();

	// output
	cout << Ans;

	return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과

간만에 BFS를 사용하는 문제여서 복습하기 좋았고,

풀이에도 큰 문제가 없었다.

 

그런데 보다시피 실행시간이 매우 오래걸렸다.

그래서 코드를 뜯어보았는데 벡터의 사용도 적었고,

구조체를 한번 사용해긴 했지만 시간에 큰 영향을 주지 않았을 것 같다.

 

내 생각에는 배열이 계속 초기화되고 새로 생성되면서 이것이 메모리를 잡아먹고

실행시간에도 많은 영향을 준 것 같다.

 

이를 최적화한다면 더욱 좋은 풀이가 될 것이다.