백준) 14868 문명 - bfs, 유니온 파인드

문명 

https://www.acmicpc.net/problem/14868

제대로 푼건지 모르겠다. 주변에 잘하시는 분들을 보면 다 유니온 파인드를 최적화하셨던데,

쌩 유니온 파인드로 제출했더니 맞긴했다.

나중에 재채점되면 틀릴 것 같지만, 일단 풀이를 공유하고자 한다.

맵에 k개의 문명 발상지가 있고, 매 턴마다 문명들은 사방향으로 진출하고, 경계선이 맞닿는다면(사방향) 해당 문명을 흡수한다.

이렇게 턴들이 진행될 때, 몇번째 턴에 모든 문명이 하나로 통일될 것인지 계산해야 한다.

예외적으로, 처음부터 k개의 발상지들이 모두 붙어있었다면, 바로 하나로 통일되고 답은 0이다.

사방향과 최소턴이라는 키워드로 일단 bfs를 쓰기로 했다.

탈출조건은, 문명이 줄고 줄어서 하나로 통일될 때 인데, 이를 구분하기 위해 유니온-파인드를 썼다.

맞닿는 경우에, 두 문명의 부모를 찾고, 다르다면 유니온하면서 문명 카운트를 하나 줄이는 것이다.

만약 카운트가 1이되면 bfs는 종료된다.

맞닿는 경우를 이중포문으로 어거지로 짠 것 같은데, 일단 맞았으니까 기분좋게 넘어간다.

#include <stdio.h>
#include <queue>
using namespace std;
 
int map[2000][2000];
int dir[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
int n, k, a, b;
 
struct civil{
    int num;
    int y, x;
};
queue<civil> init, q;
 
int p[100001];
 
int find(int x){
    if (x == p[x])
        return x;
    else
        return p[x] = find(p[x]);
}
void unite(int x, int y){
    x = find(x);
    y = find(y);
 
    if (x != y)
        p[x] = y;
}
 
int main(){
    scanf("%d %d", &n, &k);
 
    for (int i = 1; i <= k; ++i){
        scanf("%d %d", &a, &b);
        init.push({ i, b - 1, a - 1 });
        p[i] = i;
 
        map[b - 1][a - 1] = i;
    }
 
    while (!init.empty()){
        civil tmp = init.front();
        init.pop();
 
        for (int i = 0; i < 4; ++i){
            int yy = tmp.y + dir[i][0];
            int xx = tmp.x + dir[i][1];
 
            if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                continue;
 
            if (map[yy][xx] != 0){
                if (find(tmp.num) != find(map[yy][xx])){
                    unite(tmp.num, map[yy][xx]);
                    map[yy][xx] = tmp.num;
                    k--;
                }
            }
        }
        q.push({ map[tmp.y][tmp.x], tmp.y, tmp.x });
    }
 
    if (k == 1){
        printf("0");
        return 0;
    }
 
    int ans = 0;
    while (!q.empty()){
        ans++;
        int s = q.size();
        for (int i = 0; i < s; ++i){
            civil tmp = q.front();
            q.pop();
 
            for (int i = 0; i < 4; ++i){
                int yy = tmp.y + dir[i][0];
                int xx = tmp.x + dir[i][1];
 
                if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                    continue;
 
                if (map[yy][xx] != 0)
                    continue;
 
                map[yy][xx] = tmp.num;
                for (int j = 0; j < 4; ++j){
                    int yyy = yy + dir[j][0];
                    int xxx = xx + dir[j][1];
 
                    if (yyy < 0 || xxx < 0 || yyy >= n || xxx >= n)
                        continue;
 
                    if (map[yyy][xxx] != 0 && find(map[yyy][xxx]) != find(tmp.num)){
                        unite(tmp.num, map[yyy][xxx]);
                        k--;
 
                        if (k == 1){
                            printf("%d", ans);
                            return 0;
                        }
                    }
                }
                q.push({ tmp.num, yy, xx });
            }
        }
    }
}