[백준] 14868번 문명

 

[적용한 알고리즘]

BFS, 유니온 파인드

 

[아이디어]

문명 전파 한번, 문명 합치기 한번 씩 계속 돌려가면서 

문명이 1개가 되면 종료해주면 되겠다.

 

[생각의 흐름 / 절차] 

1. 문명이 붙어있는지 검사해서 인접한 문명이 있다면 서로 union 해준다. (BFS 이용)

2. 문명을 전파해준다. (BFS2 이용)

 

위 과정을 문명의 개수가 1개가 될때까지 계속 해주면 된다.

그 과정을 실행한 횟수가 구하고 싶은 답이 된다.

 

[교훈]

유니온 파인드에서도 최적화해서 시간을 단축하는 스킬들이 있던데 아직은 잘 모르겠다.

처음에 좌표들을 유니온 해주겠다는 멍청한 생각을 해서 시간을 엄청 날렸다.

당연히 문명에 이름을 붙이고 그것들을 union 해나가야한다.

구현이 개힘들었다. 플레 문제는 아직 많이 힘들다.

 

<코드>

#include <cstdio>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
    int x;
    int y;
} cord;

int Parent[100002];
int n, k;
int map[2001][2001];
int dirx[] = {1, -1, 0, 0};
int diry[] = {0, 0, 1, -1};
queue<cord> q, q2;

int Find(int x){
    if (Parent[x] == x) return x;
    return Parent[x] = Find(Parent[x]);
}

bool Merge(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y) return true; //이미 같은 문명이라면 true
    Parent[x] = y; 
    return false; 
    //다른 문명이므로 union 한 뒤 false를 리턴한다. -> 문명의 개수 1 감소.
}

void bfs(){ //문명을 합치는 BFS
    while (!q.empty()){
        int curx = q.front().x;
        int cury = q.front().y;
        q2.push({curx, cury});
        q.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (1 <= nx && nx <= n && 1 <= ny && ny <= n){
                if (map[nx][ny] > 0 && map[curx][cury] != map[nx][ny]){
                    if (!Merge(map[nx][ny], map[curx][cury])){
                        k--;
                    }
                }
            }
        }
    }
}

void bfs2(){ //문명을 전파하는 BFS
    while (!q2.empty()){
        int curx = q2.front().x;
        int cury = q2.front().y;
        q2.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (1 <= nx && nx <= n && 1 <= ny && ny <= n){
                if (map[nx][ny] == 0){
                    map[nx][ny] = map[curx][cury];
                    q.push({nx, ny});
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= k; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        map[x][y] = i;
        Parent[i] = i;
        q.push({x, y});
    }

    int ans = 0;
    while (true){
        bfs();
        if (k == 1){
            printf("%d\n", ans);
            return 0;
        }
        bfs2();
        ans++;
    }
}