14868 문명

bfs + disjoint set 문제다.

문명의 영향력은 영토 + {dx,dy}이므로 이 조건을 잘 지키면서 시작부터 연결되어 있는 경우를 조심해야 한다.

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
#pragma warning(disable:4996)
#define MAX_N 2001
 
int n, k, map[MAX_N][MAX_N];
//int xq[100001], yq[100001];
int req_union;
int dx[] = { 0, 0, 1, -1 }, dy[] = { 1, -1, 0, 0 };
int d[100001], r[100001];
 
int f(int x) {
    return x == d[x] ? x : d[x] = f(d[x]);
}
 
int u(int x, int y) {
    x = f(x);
    y = f(y);
    if (x == y) return 0;
    if (r[x] < r[y]) 
        swap(x, y);
    d[y] = x;
    if (r[x] == r[y])
        r[x]++;
    return 1;
}
 
int main() {
    queue<pair<int, int>> q;
    scanf("%d%d", &n, &k);
    req_union = k - 1;
    for (int i = 0; i < 100001; i++) d[i] = i;
    for (int i = 0, x, y; i < k; i++) {
        scanf("%d%d", &x, &y);
        map[x][y] = i + 1;
        q.push({ x, y });
        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
            if (map[nx][ny]) {
                req_union -= u(map[x][y], map[nx][ny]);
            }
        }
    }
    if (k == 1) {
        printf("0");
        return 0;
    }
    int ans = 0;
    while (q.size() && req_union) {
        int s = q.size();
        for (int i = 0; i < s; i++) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
                if (map[nx][ny] != 0) {
                    req_union -= u(map[x][y], map[nx][ny]);
                }
                else {
                    map[nx][ny] = map[x][y];
                    q.push({ nx, ny });
                    for (int k = 0; k < 4; k++) {
                        int nnx = nx + dx[k];
                        int nny = ny + dy[k];
                        if (nnx < 1 || nny < 1 || nnx > n || nny > n) continue;
                        if (map[nnx][nny]) {
                            req_union -= u(map[nx][ny], map[nnx][nny]);
                        }
                    }
                }
            }
        }
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}