BOJ 14868 문명

문명

(http://boj.kr/14868)

BFS로 지도를 채워가면서 유니온 파인드로 문명을 구별해가면 된다.

확장할 때, 인접한 곳이 이미 채워져 있다면 다른 문명인지 확인하고,

안 채워져 있다면 문명을 확장하고 그 확장된 곳에 다른 문명이 인접해 있는지를 확인한다.

#include <bits/stdc++.h>
 
using namespace std;
 
int mp[2001][2001], pr[100001], rnk[100001], dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
 
int find(int q) {
    if (pr[q] == q)
        return q;
 
    return pr[q] = find(pr[q]);
}
 
void merge(int a, int b) {
    a = find(a);
    b = find(b);
 
    if (rnk[a] > rnk[b])
        swap(a, b);
    pr[a] = b;
    if (rnk[a] == rnk[b])
        rnk[b]++;
}
 
int main() {
    int n, k, i, j, l, u, v, rst, ans = 0;
    queue<vector<int> > q;
 
    for (i = 0;i < 100000;++i)
        pr[i] = i;
 
    scanf("%d %d", &n, &k);
    rst = k;
 
    for (i = 1;i <= k;++i) {
        scanf("%d %d", &u, &v);
 
        mp[u][v] = i;
        q.push({ u, v, 0 });
 
        for (j = 0;j < 4;++j) {
            pair<int, int> nxt = { u + dx[j], v + dy[j] };
 
            if (nxt.first > 0 && nxt.first <= n && nxt.second > 0 && nxt.second <= n && mp[nxt.first][nxt.second] != 0)
                if (find(mp[u][v]) != find(mp[nxt.first][nxt.second])) {
                    merge(mp[u][v], mp[nxt.first][nxt.second]);
                    rst--;
                }
        }
    }
 
    while (rst > 1) {
        vector<int> now = q.front();
        q.pop();
 
        if (ans < now[2])
            ans = now[2];
 
        for (j = 0;j < 4;++j) {
            pair<int, int> nxt = { now[0] + dx[j], now[1] + dy[j] };
 
            if (nxt.first <= 0 || nxt.first > n || nxt.second <= 0 || nxt.second > n)
                continue;
 
            if (mp[nxt.first][nxt.second]) {
                if (find(mp[now[0]][now[1]]) != find(mp[nxt.first][nxt.second])) {
                    merge(mp[now[0]][now[1]], mp[nxt.first][nxt.second]);
                    if(--rst == 1)
                        ans = now[2];
                }
            }
            else {
                mp[nxt.first][nxt.second] = mp[now[0]][now[1]];
                q.push({ nxt.first, nxt.second, now[2] + 1 });
 
                for (l = 0;l < 4;++l) {
                    pair<int, int> nnxt = { nxt.first + dx[l], nxt.second + dy[l] };
 
                    if (nnxt.first > 0 && nnxt.first <= n && nnxt.second > 0 && nnxt.second <= n && mp[nnxt.first][nnxt.second] != 0)
                        if (find(mp[nxt.first][nxt.second]) != find(mp[nnxt.first][nnxt.second])) {
                            merge(mp[nxt.first][nxt.second], mp[nnxt.first][nnxt.second]);
                            if (--rst == 1)
                                ans = now[2] + 1;
                        }
                }
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}