[BOJ] 16234 - 인구 이동

[백준] 16234 - 인구 이동

나는 이동할 수 있는 모든 나라들은 연합을 이루어 인구이동을 할 수 있기 때문에 문제를 보자마자 Union-Find문제라고 생각했다. 과연 옳은 접근이었을지는.. 모르겠지만..
풀고 나서 문제 분류를 보니 그래프를 만들어서 푸는 것 같은데.. 유니온 파인드도 그래프를 만드는거니까 나름 맞는 접근이었던게 아닐까..?
이 문제 역시 매 인구이동마다 배열을 초기화해야 하는데 까먹어서 원인을 찾아 헤맸다,, 초기화를 반드시 잊지 말자..

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string.h>
#include <queue>
#include <functional>
#define INF 987654321
using namespace std;
typedef pair<int, int> PII;

const int dr[4] = { 0, 0,1,-1 }, dc[4] = { 1, -1, 0, 0 };
int n, l, r, population[55][55], par[3605], sum[3605];

bool is_in_range(int x, int y) {
    return x >= 0 && x < n&& y >= 0 && y < n;
}

int get_number(int x, int y) {
    return x * 55 + y + 1;
}

int find(int now) {
    if (par[now] == 0) return now;
    return par[now] = find(par[now]);
}

void merge(int x, int y) {
    if (find(x) == find(y)) return;
    par[find(x)] = find(y);
    find(x);
}

int main(void) {
    scanf("%d %d %d", &n, &l, &r);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", population[i] + j);
        }
    }
    
    int cnt = 0;

    while (++cnt) {
        bool ck = false;
        memset(sum, 0, sizeof(sum));
        memset(par, 0, sizeof(par));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 4; k++) {
                    int x = i + dr[k], y = j + dc[k];
                    if (!is_in_range(x, y)) continue;
                    int gap = abs(population[i][j] - population[x][y]);
                    if (gap >= l && gap <= r) {
                        merge(get_number(i, j), get_number(x, y));
                        ck = true;
                    }
                }
            }
        }
        if (!ck) {
            printf("%d", cnt - 1);
            break;
        }
        map<int, int> association;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                association[find(get_number(i, j))]++;
                sum[find(get_number(i, j))] += population[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                population[i][j] = sum[find(get_number(i, j))] / association[find(get_number(i, j))];
            }
        }
    }
    return 0;
}