병렬 이분 탐색

작성일 | In

서론

어떤 문제에서 답이 단조성을 가질 때는 binary search 등을 이용한 parametric search로 빠르게 답을 구할 수 있습니다.
병렬 이분 탐색(Parallel Binary Search, PBS)는 parametric search의 각 결정 문제를 스위핑 하듯이 풀 수 있는 몇몇 경우에 적용할 수 있는 기법입니다. 말로 설명하기 힘드니 문제와 함께 소개하겠습니다.

BOJ1396 크루스칼의 공

문제 링크

문제에서 $Q = 1$이라고 가정하고, 이분 탐색을 이용해 문제를 풀어봅시다.

최소 온도를 구할 것이기 때문에, 다음과 같은 결정 문제를 해결하면 문제를 풀 수 있습니다.
고유값이 mid 이하인 간선만 사용해 x에서 y로 갈 수 있는가?
최소 온도만 구해준다면 움직일 수 있는 범위는 union-find 등의 자료구조로 쉽게 알 수 있습니다.

시간 복잡도를 분석해보면 union-find를 사용하기 때문에 각 결정 문제를 해결하는데 $O(M log N)$이 소요되고, 결정 문제를 O(log M)번 해결해야 하므로 총 시간 복잡도는 $O(M log N log M)$입니다.
문제에서 주어진대로 Q ≤ 10만이라면 $O(QM log N log M)$이라는 TLE나기 좋은 시간 복잡도가 나옵니다.

이제부터 PBS를 이용해 시간 복잡도를 줄이는 방법을 알아봅시다.

서론에 있는 내용을 다시 보면, 각 결정 문제를 스위핑 하듯이 풀 수 있는 경우 에 PBS를 사용할 수 있다고 했습니다. 크루스칼의 공 문제도 간선들을 오름차순으로 스위핑 하듯이 결정 문제를 해결하기 때문에 PBS를 적용할 수 있습니다.

이 문제에서 결정 문제를 풀 때 우리가 관심이 있는 것은, mid 시점에 x에서 y로 갈 수 있는지 여부입니다. 그리고 $M$개의 간선을 쭉 훑어주면 모든 mid 시점을 고려할 수 있습니다.

여기에서 PBS의 아이디어가 나옵니다. 각 쿼리를 따로 처리할 필요 없이, mid가 같은 것끼리 묶어서 처리하고, 한 번의 스위핑으로 모든 mid값들을 고려해주는 것입니다.
스위핑을 한 번 하면 $Q$개의 쿼리에 대해 각각 한 번씩 결정 문제를 해결해준 것과 같은 효과를 얻을 수 있습니다. $O(log M)$번 스위핑하면 $Q$개의 쿼리의 답을 모두 구할 수 있겠지요. 이것이 Parallel Binary Search입니다.

한 번 스위핑 하는데 걸리는 시간을 분석해봅시다.
유사 크루스칼 알고리즘을 돌리는데 $O(M log N)$, $Q$개의 쿼리에 대해 각각 결정 문제를 푸는데 $O(QlogN)$, 총 $O((M+Q)logN)$이 걸립니다. union-find최적화를 잘 해주면 $O((M+Q) \alpha (N))$으로 줄일 수 있겠네요.

이러한 스위핑을 $O(log M)$번 하기 때문에 총 시간 복잡도는 $O((N+Q) \alpha(N) log M)$입니다.

구현

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef pair<int, int> p;

struct Edge{
    int s, e, x;
    bool operator < (const Edge &t) const {
        return x < t.x;
    }
    Edge(){}
    Edge(int s, int e, int x) : s(s), e(e), x(x) {}
};

struct UF{
    int par[101010];
    int sz[101010];
    void init(){
        for(int i=0; i<101010; i++) par[i] = i, sz[i] = 1;
    }
    int find(int v){
        return v == par[v] ? v : par[v] = find(par[v]);
    }
    bool merge(int u, int v){
        u = find(u), v = find(v);
        if(u == v) return 0;
        par[u] = v;
        sz[v] += sz[u];
        return 1;
    }
};

Edge edge[101010];
p qry[101010];

int l[101010], r[101010], res[101010][2]; //pbs
UF uf;
vector<int> g[101010];

void init(){ for(int i=0; i<101010; i++) g[i].clear(); }

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, q; cin >> n >> m;
    for(int i=1; i<=m; i++) cin >> edge[i].s >> edge[i].e >> edge[i].x;
    cin >> q;
    for(int i=1; i<=q; i++) cin >>qry[i].x >> qry[i].y;

    sort(edge+1, edge+m+1);
    for(int i=1; i<=q; i++) l[i] = 1, r[i] = m + 1;

    while(1){
        init();
        bool flag = 0;
        for(int i=1; i<=q; i++) if(l[i] != r[i]){ //mid = i인 쿼리들 g[i]에 모으기
            flag = 1; g[l[i] + r[i] >> 1].push_back(i);
        }
        if(!flag) break; //더 이상 처리할 쿼리가 없으면 종료

        uf.init();
        for(int i=1; i<=m; i++){
            int s = edge[i].s, e = edge[i].e, x = edge[i].x;
            uf.merge(s, e);
            for(auto j : g[i]){ //i번째 간선까지 연결하고 결정 문제 해결
                int a = uf.find(qry[j].x), b = uf.find(qry[j].y);
                if(a == b){
                    r[j] = i;
                    res[j][0] = x, res[j][1] = uf.sz[uf.find(a)];
                }else{
                    l[j] = i + 1;
                }
            }
        }
    }
    for(int i=1; i<=q; i++){
        if(l[i] == m+1) cout << "-1\n";
        else cout << res[i][0] << " " << res[i][1] << "\n";
    }
}

연습 문제

BOJ16977 히스토그램에서 가장 큰 직사각형과 쿼리 : 풀이
BOJ15957 음악 추천 : 풀이