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

[16234번 인구 이동]
https://www.acmicpc.net/problem/16234

개인적으로 플레5 난이도의 큐빙보다 어려웠다.
[5373 큐빙]
https://www.acmicpc.net/problem/5373

풀이

아이디어를 떠올리기까지는 오래 걸리지 않았다. 2중 for문으로 나라 전체를 돌면서 BFS(혹은 DFS)를 통해 마치 바이러스가 퍼지듯이 연합을 찾아주고, 각각의 연합에 맞게 평균 인구 수를 대입해준다.
더 이상 인구 이동이 일어나지 않을 때까지 반복하고 며칠 간 이동이 일어났는지 출력하면 된다.

주의할 부분은 하루에 연합이 여러 개 생성될 수 있고, 각 연합마다 평균 인구 수가 다를 수 있다는 점이다. 처음에 이 부분을 생각치 못했고 그대로 돌아올 수 없는 강을 건넜다. 이 부분을 떠올렸을 때는 이미 너무 녹초가 되어있어서 더 이상의 코딩이 불가능했다. 다음 날 다시 풀었고, 다행히 정답을 맞출 수 있었다.

매우 간략한 수도코드로 적어보자면 다음과 같다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int n,L,R;
int map[52][52];
int open[52][52];
int dr[] = {0,1,0,-1};
int dc[] = {1,0,-1,0};
int day = 0;
int unions = 0;
vector<int> avgs;

bool needMove() {
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			for(int d=0;d<4;++d) {
				int ni,nj;

				ni = i+dr[d];
				nj = j+dc[d];

				int home = map[i][j];
				int adj = map[ni][nj];
				if(L <= abs(home-adj) && abs(home-adj) <= R) {
					return true;
				}		
			}
		}
	}

	return false;
}

void bfs(int r, int c) {
	int countries = 1;
	int population = map[r][c];

	queue<pair<int,int> > q;
	q.push(make_pair(r,c));
	open[r][c] = unions;

	while(!q.empty()) {
		pair<int,int> p = q.front();
		q.pop();

		r = p.first;
		c = p.second;

		for(int d=0;d<4;++d) {
			int nr,nc;
			nr = r+dr[d];
			nc = c+dc[d];

			if(open[nr][nc]) {
				continue;
			}

			int home = map[r][c];
			int adj = map[nr][nc];
			if(L <= abs(home-adj) && abs(home-adj) <= R) {
				open[nr][nc] = unions;
				countries++;
				population += map[nr][nc];
				q.push(make_pair(nr,nc));
			}
		}
	}

	avgs.push_back(population / countries);

	return;
}

void sol() {

	while(true) {
		memset(open,0,sizeof(open));
		if(!needMove()) {
			break;
		}

		day++;
		unions = 0;
		avgs.clear();
		avgs.push_back(-1); // dummy value

		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				if(!open[i][j]) {
					for(int d=0;d<4;++d) {
						int ni,nj;

						ni = i+dr[d];
						nj = j+dc[d];

						int home = map[i][j];
						int adj = map[ni][nj];
						if(L <= abs(home-adj) &&  abs(home-adj) <= R) {
							if(!open[ni][nj]) {
								unions++;  // increase the number of unions
								bfs(i,j);
							}
						}
					}
				}
			}
		}

		// average the population
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				if(open[i][j]) {
					int unionNum = open[i][j];
					map[i][j] = avgs[unionNum];
				}
			}
		}

	}
	
	return;
}

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

	scanf("%d%d%d", &n,&L,&R);
	for(int i=0;i<52;++i) {
		for(int j=0;j<52;++j) {
			map[i][j] = INF;
		}
	}

	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			scanf("%d", &map[i][j]);
		}
	}

	sol();
	printf("%d\n", day);
	
	return 0;
}

채점 결과