[Baekjoon] 16234번: 인구 이동

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

16234번: 인구 이동

 

---

 

문제 해결 과정

착안

너비 우선 탐색(breadth-first search, BFS) 알고리즘을 응용하여 날짜 별로 연합이 존재할 수 있는지 탐색해보고, 연합이 존재한다면 각 연합 별로 연합에 속하는 나라들의 인구를 산술평균 값으로 갱신하는 과정을 통해 문제를 해결하고자 하였다.

 

연합이 존재할 수 있는지 판단하는 과정에서, 인접한 나라와 직접적으로 국경선이 개방되어 연결되지 않더라도 우회하여 연결될 수 있기 때문에(ex: 'ㄷ' 자 모양으로 국경선이 개방되는 경우 등) 일반적인 너비 우선 탐색과 같은 방식으로 인접한 나라를 나타내는 노드의 방문 여부를 표시하지 않고 약간 다른 방식으로 방문 여부를 표시하는 것이 필요하다.

* 참고) 위와 같은 특수한 경우를 확인하려면 동일한 노드에 대해 여러 방향에서 접근하는 과정들을 모두 확인해야 한다.

 

구현

너비 우선 탐색을 위한 큐(queue) 자료 구조를 활용함에 있어서, 위에서 설명한 부분에 의해 동일한 노드가 중복으로 큐에 삽입되는 과정이 필연적으로 발생하게 되므로 이때 가능한 한 불필요한 계산을 줄이는 데에 중점을 두어 구현해보았다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <memory.h>

using namespace std;

struct Coord
{
	int X;
	int Y;
};

int N, L, R, Sum, Days;
int A[50][50];
bool Visited[50][50];

int DX[4] = { 1, 0, -1, 0 };
int DY[4] = { 0, 1, 0, -1 };

queue<Coord> Queue;
vector<Coord> Union;

void CheckAdjacent(int x, int y, int i)
{
	int row = y + DY[i];
	int col = x + DX[i];

	if (row < 0 || row > N - 1 ||
		col < 0 || col > N - 1 ||
		Visited[row][col])
		return;

	int diff = abs(A[y][x] - A[row][col]);
	if (diff >= L && diff <= R)
	{
		Visited[row][col] = true;
		Sum += A[row][col];
		Union.emplace_back(Coord{ col, row });
		Queue.emplace(Coord{ col, row });
	}
}

bool Unify(int x, int y)
{
	Visited[y][x] = true;
	Sum = A[y][x];

	Union.clear();
	Union.emplace_back(Coord{ x, y });
	Queue.emplace(Coord{ x, y });
	while (!Queue.empty())
	{
		Coord coord = Queue.front();
		Queue.pop();

		for (int i = 0; i < 4; i++)
			CheckAdjacent(coord.X, coord.Y, i);
	}

	int Num = Sum / Union.size();
	for (const Coord& c : Union)
		A[c.Y][c.X] = Num;

	return Union.size() > 1;
}

int main()
{
	cin >> N >> L >> R;

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

	while (true)
	{
		memset(Visited, false, 50 * 50);
		bool bExistUnion = false;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (!Visited[i][j])
					bExistUnion |= Unify(j, i);

		if (bExistUnion)
			Days++;
		else
			break;
	}

	cout << Days << "\n";
	return 0;
}

 

실행 결과