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

문제

예시

 

풀이

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

int N, L, R;
int country[100][100];
bool isVisited[100][100] = {false};
bool isCanMove = true;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1 };

void BFS(int x, int y)
{
	if (isVisited[x][y]) return;
	isVisited[x][y] = true;

	queue<pair<int, int>> q;
	queue<pair<int, int>> checkq;

	q.push(make_pair(x, y));
	checkq.push(make_pair(x, y));

	int peopleSum = 0;
	peopleSum += country[x][y];
	int openCountryCnt = 0;
	openCountryCnt++;

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

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

			if (nx >= 0 && nx < N && ny >= 0 && ny < N)
			{
				if (peopleSub >= L && peopleSub <= R && !isVisited[nx][ny])
				{
					isVisited[nx][ny] = true;
					openCountryCnt++;
					peopleSum += country[nx][ny];
					isCanMove = true;
					q.push(make_pair(nx, ny));
					checkq.push(make_pair(nx, ny));
				}
			}
		}
	}

	while (!checkq.empty())
	{
		int x, y;
		x = checkq.front().first;
		y = checkq.front().second;

		int diviedPeople = peopleSum / openCountryCnt;
		country[x][y] = diviedPeople;
		checkq.pop();
	}
}

int main()
{
	int count(0);

	cin >> N >> L >> R;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> country[i][j];
		}
	}

	while (true)
	{
		isCanMove = false;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				BFS(i, j);
			}
		}
		if (!isCanMove) break;
		count++;
		memset(isVisited, false, sizeof(isVisited));
	}

	cout << count;

	return 0;
}

 

설명

특정 나라부터 인접한 나라를 우선적으로 파악하는 과정을 위해 BFS(너비 우선 탐색) 알고리즘을 사용한다.

 

먼저 입력값을 받을 N, L, R 과 나라 별 인구수를 받는 배열 country, 특정 노드 방문 여부를 확인할 bool배열 isVisited, 국경이 열리고 인구가 움직일 수 있는 상태를 나타낼 isCanMove, 마지막으로 BFS의 진행 방향을 결정할 방향 벡터 dx/dy를 전역으로 초기화한다.

설계 구조 관점에서는 사실 지역 변수로 초기화 후 매개변수를 통해 값을 전달하는 구조가 더 바람직하지만, 빠른 구현을 요구하는 코딩 테스트의 특성과 가독성을 위해 전역으로 초기화한다.

 

Main 문에서는 입력값 N, L, R, country[][]를 입력받고, BFS에 진입하기 위한 조건을 마련한다.

첫 입력이 완성된 상태를 기준으로는 인구가 움직일 수 없기에 isCanMove 변수를 false 로 바꾸고, 국가 중 가장 첫번째 인덱스 [0][0] 부터 BFS에 진입한다.

결과적으로 Main 에서는 BFS가 종료되고 난 이후의 상태에서 인구가 움직인 횟수를 측정하는 역할을 수행한다.

 

BFS 함수에서는 본격적으로 국가별로 인구가 움직이는 탐색 과정을 진행한다.

Main 에서 BFS가 시작된 인덱스를 x, y로 받아 방문 여부를 체크해주고, 현재 인덱스를 큐에 넣어준다.

 

이 큐(q, checkq) 는 각각 국가별 인구의 이동 조건과 총합을 체크하기 위함과, 실제 이동 후의 인구수를 배분하기 위함 두 동작을 위해 사용한다.

 

첫번째 반복문 while(!q.empty()) 에서는 q의 첫번째 요소를 꺼내어 방향 벡터를 통해 인접한 국가들과 인구수 차를 비교한다.

이후 모든 조건이 만족되면 현재 탐색중인 노드 또한 큐에 넣어 인구수를 배분할 요소로 취합하는 과정을 진행한다.

 

두번째 반복문 while(!checkq.empty()) 에서는 첫번째 반복문을 통해 인구가 이동할 국가가 모두 선정이 끝난 상황에서 시작된다.

따라서 checkq의 첫번째 요소부터 꺼내어 인구가 이동하고 난 후(int diviedPeople = peopleSum / openCountryCnt;) 의 수를 현재 요소의 국가에 할당하는 과정을 반복한다.

 

이 모든 과정을 진행하고 나면 Main 문의 while(true)가 끝난 시점으로 돌아오게 되며, 이후 총 이동한 횟수 count 를 출력하고 로직이 종료된다.