[BOJ / 16234 / C++] 인구 이동

인구 이동 문제다.

 

다 풀고나서 알았는데 삼성 기출문제란다. ㅎㅎ 시간내에 풀었다.

 

사실 전날까지 MST를 너무 열심히 풀어서인지 아주 자연스럽게 Union-Find로 풀었는데 BFS로 푸는 문제였나보다.

 

풀이가 죄다 BFS... 완탐문제인줄 알았다.

 

어찌됐던 내가 생각한 알고리즘은

 

1. 맵 입력을 받는다.

2. 반복문 시작

3. Union-Find용 연합(group)과 연합을 구성하는 국가의 수(groupCnt, 인구수 x)을 각각 연합 인덱스와 1로 초기화한다.

> 인덱스는 나같은 경우 그냥 좌표 그대로 쓰려고 (y*N + x) 형태로 인덱스를 정했다.

> 3x3 맵의 (1,0)에 위치한 국가의 인덱스는 3이 된다.

4. 수평(우측)과 수직(하측) 국경을 반복문으로 확인하고 각 좌표별로 열린 국가를 찾아 연합 후보 큐(unions)에 넣는다.

5. [ 만약에 연합 후보 큐가 비어있다면 여기서 나온다 ]

6. 모든 좌표를 확인했으면 연합 한다.

7. 연합 보스(?)를 따로 큐(bosses)에 저장해놓고 보스를 제외한 맵(각 국가별 인구수)을 갱신한다.

> 별도의 변수를 쓰지 않고 갱신시 보스 정보를 그대로 사용하기 위해서 보스를 따로 큐에 저장하고 나중에 갱신해준다.

8. 저장되어 있던 보스들의 맵(인구수) 정보를 갱신해준다.

9. 한 턴을 끝내고 2번으로 돌아가 다시 시작한다.

10. 반복문 종료

 

이렇게 풀어주면 되는데 이러면 백준에서 72ms로 나온다.

 

최적화된 BFS가 12ms정도 나오는 것 같아서 뭐 문제될 정돈 아니지만 BFS로 접근이 더 맞았을 것 같다.

 

내 알고리즘의 경우 흐름은 쉽지만 매 턴마다 N^2짜리 루프를 4번이나 돌아서...

 

#include <iostream>
#include <queue>
using namespace std;

#define HORIZONTAL 0
#define VERTICAL 1
#define ABS(a,b) (a - b > 0 ? a - b : b - a)

int map[50][50];
int group[50][50];
int groupCnt[50][50];

int N, L, R;
int T = 0;

int isHorizontalOpen(int y, int lx, int rx)
{
	int l = map[y][lx];
	int r = map[y][rx];
	int d = ABS(l, r);

	return d >= L && d <= R;
}

int isVerticalOpen(int x, int ty, int by)
{
	int t = map[ty][x];
	int b = map[by][x];
	int d = ABS(t, b);

	return d >= L && d <= R;
}

int findBoss(int y, int x)
{
	return group[y][x] == N * y + x ? N * y + x : findBoss(group[y][x] / N, group[y][x] % N);
}

int setUnion(int y1, int x1, int y2, int x2)
{
	int aBoss = findBoss(y1, x1);
	int bBoss = findBoss(y2, x2);
	if (aBoss == bBoss) return 0;

	group[bBoss / N][bBoss % N] = aBoss;

	groupCnt[aBoss / N][aBoss % N] += groupCnt[bBoss / N][bBoss % N];
	groupCnt[bBoss / N][bBoss % N] = 0;

	map[aBoss / N][aBoss % N] += map[bBoss / N][bBoss % N];
	map[bBoss / N][bBoss % N] = 0;
	return 1;
}

int main() {
	cin >> N >> L >> R;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			cin >> map[y][x];

	while (T <= 2000)
	{
		queue<pair<pair<int, int>, pair<int, int>>> unions;

		for (int y = 0; y < N; y++)
			for (int x = 0; x < N; x++)
			{
				group[y][x] = N * y + x;
				groupCnt[y][x] = 1;
			}	

		for (int type = 0; type < 2; type++)
			for (int y = 0; y < (type == HORIZONTAL ? N : N - 1); y++)
				for (int x = 0; x < (type == VERTICAL ? N : N - 1); x++)
				{
					if (type == HORIZONTAL)
					{
						if (isHorizontalOpen(y, x, x + 1)) unions.push({ {y, x}, {y, x + 1} });
					}
					else if (type == VERTICAL) 
					{
						if (isVerticalOpen(x, y, y + 1)) unions.push({ {y, x}, {y + 1, x} });
					}
				}

		if (unions.empty()) break;
		while (!unions.empty())
		{
			int y1 = unions.front().first.first;
			int x1 = unions.front().first.second;
			int y2 = unions.front().second.first;
			int x2 = unions.front().second.second;
			unions.pop();
			setUnion(y1, x1, y2, x2);
		}

		queue<pair<int, int>> bosses;

		for (int y = 0; y < N; y++)
			for (int x = 0; x < N; x++)
				if (map[y][x]) bosses.push({ y,x });

		for (int y = 0; y < N; y++)
			for (int x = 0; x < N; x++)
			{
				if (map[y][x]) continue;
				int boss = findBoss(y, x);
				int yBoss = boss / N;
				int xBoss = boss % N;
				map[y][x] = map[yBoss][xBoss] / groupCnt[yBoss][xBoss];
			}

		while (!bosses.empty())
		{
			int y = bosses.front().first;
			int x = bosses.front().second;
			bosses.pop();
			map[y][x] /= groupCnt[y][x];
		}

		T++;
	}

	cout << T;

	return 0;
}