1) 문제 분석
문제의 핵심은 다음과 같다: 1.조건에 따라 가능한 국경선을 모두 연다 2.각 연합의 인구수를 새로 계산한다 3.인구 이동이 없을 때 까지 1~2를 반복한다.
각 국가들이 어떤 연합에 속해 있는지를 알고, 한 연합의 전체 인구수를 계산해서 각 국가의 인구수를 새로 계산해야 한다.
2) 알고리즘
국가 A와 국가 B 사이의 국경선이 열리면, B는 A가 속한(혹은 반대로) 연합에도 자동으로 속하게 된다. 이러한 문제 조건을 보고, disjoint set을 활용하는 것이 적절하다고 생각하였다. 국가 사이의 국경선이 사라지는 것은 두 국가가 속한 set을 join하는 것과 같으며, join하는 과정에서 연합에 속한 국가 수와 전체 인구 수를 기록하면 해결할 수 있을 것 같았다. 필요한 자료구조들을 다음과 같다:
//global variables
int nations[2500];
int nations_pop[2500];
int sum_pop[2500];
가능한 최대 국가 수가 50*50이므로 각 배열의 길이를 2500으로 설정해주었다.
nations 배열은 각 국가가 어떤 연합에 속하는지 알려준다. 즉, disjoint set에서 부모 노드를 가리킨다. 부모 노드를 계속 따라가다 보면 set의 루트 노드를 만날 수 있다. 루트 노드의 값은 음수인데, 이 값의 절대값은 해당 set의 노드 개수(해당 연합에 속한 국가 수)이다.
nations_pop 배열은 각 국가의 인구수를 저장한다. 인구 이동이 끝나고 연합의 인구수가 계산될 때 마다 새로 갱신된다.
sum_pop 배열은 각 연합의 총 인구수를 저장한다. 예를 들어, 어떤 연합 set의 루트 노드가 i라면, sum_pop[i]의 값은 i가 루트인 set의 총 인구수가 된다.
대략적인 알고리즘은 다음과 같다:
2차원 배열로 입력되는 각 국가의 인구 수를 1차원 배열 형식(nations_pop)으로 저장한다. 가령, 4*4 크기의 2차원 배열은 길이가 16인 1차원 배열로 저장된다. sum_pop 배열의 값도 nations_pop의 값으로 초기화 해준다. 아직 어떤 국가도 연합에 속해 있지 않기 때문에 nations 배열의 값은 전부 -1로 설정해준다.
첫 번째 국가부터 순회를 시작한다. 위,왼쪽,아래,오른쪽 순으로 국가가 있는지 확인하고(인덱스 범위를 체크해주고), 국가가 있다면 인구 차이가 범위 내에 속하는지 확인한다. 만약 그렇다면, 두 국가가 속한 set을 join한다. 이 때, united라는 변수를 사용하여, 연합이 적어도 한 개 존재함을 나타낸다.
모든 국가에 대해 국경선 처리가 끝났고 united의 값이 true라면, 다시 모든 국가를 순회하면서 각 국가 인구 수를 새로 계산해준다. 이 때, 각 국가가 속한 set의 parent node를 통해 연합에 속한 인구 수와 국가 수를 알 수 있다. 다시 sum_pop 값을 nations_pop 값으로 초기화 해주고, nations의 값 또한 전부 -1로 초기화한다. 이와 같은 실행을 united가 false가 될 때까지 반복한다.
인구 수를 업데이트 해줄 때 마다 count라는 변수를 사용하여 인구 이동이 일어난 횟수를 기록하도록 하였다.
3) 코드
#include <iostream>
using namespace std;
int nations[2500]; //disjoint sets
int nations_pop[2500]; //population of each nation
int sum_pop[2500]; //total population of each union
//directions: up,left,down,right
int dir_x[] = {-1,0,1,0};
int dir_y[] = {0,-1,0,1};
//check if the indices are within the valid range
bool isInRange(int r, int c, int n){
return (0 <= r && r < n && 0 <= c && c < n);
}
/**
* find root node of the set that contains x
* @param x index of a node
* @return the index of the root node
*/
int parent(int x){
//follow the parent nodes
while(nations[x]>=0)
x = nations[x];
return x;
}
/**
* join two disjoint sets
* @param x index of a node
* @param y index of a node
*/
void join(int x, int y){
//find root node of each set
int xp = parent(x);
int yp = parent(y);
//if root nodes are same, they are already in the same set
if(xp==yp) return;
//nations[xp] has bigger population
if(nations[xp] < nations[yp]){
//add total # of nations in set yp to total # of nations in set xp
nations[xp] += nations[yp];
//set yp is attached to set xp
nations[yp] = xp;
//update total population of the union
sum_pop[xp] += sum_pop[yp];
}
//nations[yp] has bigger population or both are the same
else{
//add total # of nations in set xp to total # of nations in set yp
nations[yp] += nations[xp];
//set xp is attached to set yp
nations[xp] = yp;
//update total population of the union
sum_pop[yp] += sum_pop[xp];
}
}
int main(){
int N, L, R; //N: size of space, L: lower bound, R: upper bound
int total; //total number of nations
bool united; //true if at least one union has been created
int count = 0; //number of migration happened
//get input data
cin >> N;
cin >> L;
cin >> R;
total = N*N;
//initialize nations, nations_pop, sum_pop
for(int i=0; i<total; i++) {
cin >> nations_pop[i];
nations[i] = -1;
sum_pop[i] = nations_pop[i];
}
united = true;
//repeat until no migration happens
while(united) {
united = false;
//look through every nation and see if it forms union with its neighbor nations
for (int k = 0; k < total; k++) {
int i = k / N; int j = k % N; //indices as in 2d array
//search for neighbor nations upwards,leftwards,downwards,rightwards
for (int l = 0; l < 4; l++) {
//check if the indices are not out of range
if (isInRange(i + dir_x[l], j + dir_y[l], N)) {
int index = (i + dir_x[l]) * N + (j + dir_y[l]);
//calculate the difference between population of the two nations
int diff = abs(nations_pop[k] - nations_pop[index]);
//if the difference is within the range
if (L <= diff && diff <= R) {
//join them into one union
join(k, index);
united = true;
}
}
}
}
//if at least one union has been formed
if(united){
count++;
//update population of each nation
for(int k=0; k<total; k++) {
int p = parent(k);
//(total population of the union/total # of nations in the union)
nations_pop[k] = sum_pop[p] / (nations[p]*(-1));
}
//initialize sum_pop and nations for the next calculation
for(int k=0; k<total; k++){
sum_pop[k] = nations_pop[k];
nations[k] = -1;
}
}
}
//print out the result
cout << count;
}
4) 주의할 점 및 깨달은 점
1. join 할 때 두 element가 같은 set에 속해있는지 먼저 체크한다.
2. 처음에 한 번 루프를 돌고나서 sum_pop과 nations 배열을 초기화 해주지 않아서 틀린 결과가 나왔다. 반복문을 실행할 때는 항상 어떤 변수들이 변하는지, 변한값이 그대로 유지되어도 괜찮은지 등을 체크해주어야 할 것 같다
3. 다른 사람들의 코드를 살펴보니 dfs/bfs를 사용한 경우가 많아 보였다. 그 방법은, 한 국가에서 시작하여 상하좌우 칸들 중 이동할 수 있는 칸들로 하나의 spanning tree를 만드는 것이다. 하나의 연합이 이렇게 완성되면, 다음 국가로 넘어가서 같은 일을 수행해준다. 이 경우, 최적화를 잘 하지 않는 이상 수행시간이 비교적 큰 것 같다.
4. 국가를 하나씩 살펴볼 때, 각 국가의 오른쪽과 아래쪽 국가들 사이의 국경선에 대해서만 고려하면, 중복계산을 줄일 수 있다. 즉, 각 칸에서 오른쪽 칸과 아래칸만 살펴보도록 해보았다.
int dir_x[] = {0,1};
int dir_y[] = {1,0};
이렇게 되면 for문도 2번만 수행하면 된다. 수정 결과, 시간이 80ms에서 60ms로 감소하였다.
5.nations, nations_pop, sum_pop 배열들을 각각 크기 N 만큼 동적할당하도록 수정해보았는데 시간 초과가 되었다. 이번에는 nations 배열만 동적할당을 하도록 수정했는데 시간 초과 없이 잘 돌아갔다. 검색해보니까 확실히 동적 할당이 많이 느린 작업이라 그런 것 같다.
“Dynamic memory allocation and deallocation are very slow operations when compared to automatic memory allocation and deallocation. In other words, the heap is much slower than the stack. In addition, dynamic allocation has a per-allocation overhead, causes virtual memory fragmentation, and causes bad data locality of reference, with the ensuing bad usage of both the processor data cache and virtual memory space.” 출처