Algorithm/BOJ

KOI 2017 고등부 2번 / 문명 - 14868

jhg0406 2020. 9. 12. 21:55
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <queue>
using namespace std;
 
int N, K;
vector<vector<int>> arr;
queue<pair<int, int>> Q[2];
int xarr[4] = {0, 0, 1, -1};
int yarr[4] = {1, -1, 0, 0};
bool eFlag = true;
 
struct DisjointSet {
 
    vector<int> parent, rank;
    int tNum;
 
    DisjointSet() : parent(K), rank(K, 0), tNum(K) {
        for(int i = 0; i<K; ++i)
            parent[i] = i;
    }
 
    int find(int u) {
        if(parent[u] == u) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if(u == v) return;
        if(rank[u] < rank[v]) swap(u, v);
        parent[v] = u;
        if(rank[u] == rank[v]) ++rank[u];
        --tNum;
        if(1 == tNum) eFlag = false;
    }
};
 
bool check(int u, int v) {
    if(u < 1 || u > N || v < 1 || v > N) return false;
    return true;
}
 
void init(DisjointSet& set) {
    arr = vector<vector<int>>(N+1, vector<int>(N+1, -1));
    Q[0] = Q[1] = queue<pair<int, int>>();
    int u, v;
    for(int i = 0; i<K; ++i) {
        cin >> u >> v;
        arr[u][v] = i;
        for(int j = 0; j<4; ++j) {
            int au = u + xarr[j];
            int av = v + yarr[j];
            if(check(au, av))
                if(arr[au][av] != -1) set.merge(arr[u][v], arr[au][av]);
        }
        Q[0].push(make_pair(u, v));
    }
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
 
    cin >> N >> K;
    DisjointSet set;
    init(set);
    int cnt = 0;
 
    while(eFlag) {
        while(eFlag && !Q[cnt%2].empty()) {
            int x = Q[cnt%2].front().first;
            int y = Q[cnt%2].front().second;
            Q[cnt%2].pop();
            for(int i = 0; i<4; ++i) {
                int nx = x+xarr[i], ny = y+yarr[i];
                if(check(nx, ny)) {
                    if(arr[nx][ny] == -1) {
                        Q[(cnt+1)%2].push(make_pair(nx, ny));
                        arr[nx][ny] = arr[x][y];
 
                        for(int j = 0; j<4; ++j) {
                            int nnx = nx+xarr[j], nny = ny+yarr[j];
                            if(check(nnx, nny)) {
                                if(arr[nnx][nny] != -1) set.merge(arr[x][y], arr[nnx][nny]);
                            }
                        }
                    }
                }
            }
        }
        ++cnt;
    }
    cout << cnt;
}
 cs

 

 

 

 

 

www.acmicpc.net/problem/14868

 

14868번: 문명

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지�

www.acmicpc.net

 

 

 

 

 

문명

BFS와 유니온-파인드로 해결할 수 있습니다. 주의할 점은 문명끼리 이어질때는 추가된 영토에 인접한 다른 문명이 있으면 이어지는데 맨 처음 주어지는 데이터에선 인접해 있더라도 같은 문명으로 취급되지 않는 데이터가 들어오기 때문에 인접한 문명끼리 하나의 문명으로 합쳐주는 전처리과정이 필요합니다.