백준6181 플러드 필 (Flood Fill)

작성일 | In

문제 링크

  • http://icpc.me/6181

문제 출처

  • 2008 USACO US Open Gold 3번

사용 알고리즘

  • 분할 정복

시간복잡도

  • $O(N \log N)$

풀이

맨허튼 거리($L_1$, $d = \vert x_1 - x_2\vert + \vert y_1 - y_2\vert$)를 45도 회전시키면 체비셰프 거리($L_{\infty}$, $d = \max(\vert x_1 - x_2\vert, \vert y_1 - y_2\vert)$)가 됩니다.
입력으로 주어진 좌표 $(x, y)$를 $(x+y, x-y)$로 변환한 다음, 체비셰프 거리에서 해결합시다.

좌표들을 x좌표 기준으로 정렬합시다.
가운데 있는 점 $m$을 잡고, x좌표가 $[x_m - k, x_m + k]$ 구간에 있는 점들만 고려할 것입니다. 해당 점들을 y좌표 순으로 정렬하고, 투포인터 느낌으로 쭉 훑어주면서 거리가 k 이하인 점을 Union하면 됩니다.

x좌표 기준으로 정렬되어 있는 점을 다시 y좌표 순으로 정렬하는 것이 문제가 될 수 있는데, 분할 정복의 “정복” 단계에서 Merge Sort 하듯이 정렬해주면 됩니다.

$T(N) = 2T(N/2) + O(N)$이므로 $O(N \log N)$에 문제를 해결할 수 있습니다.

전체 코드

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

typedef long long ll;

struct Point{
    ll x, y, i;
    Point() : Point(0, 0, 0) {}
    Point(ll x, ll y, ll i) : x(x), y(y), i(i) {}
    bool operator < (const Point &t) const { return x < t.x; }
};
struct UF{
    vector<int> par, sz; int cnt;
    void init(int n){
        par.resize(n+1); iota(all(par), 0);
        sz.resize(n+1);  fill(all( sz), 1);
        cnt = n;
    }
    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 false;
        par[u] = v; sz[v] += sz[u]; cnt--;
        return true;
    }
    int get_max(){ return *max_element(all(sz)); }
};
inline int dst(const Point &p1, const Point &p2){
    return max(abs(p1.x-p2.x), abs(p1.y-p2.y));
}

int n, k;
Point pt[101010], tmp[101010];
UF uf;

void f(int s, int e){
    if(s >= e) return;
    int m = s + e >> 1;
    int x_m = pt[m].x;
    f(s, m); f(m+1, e);

    deque<int> u, v;
    int l = s, r = m+1, pv = s;

    while(l <= m || r <= e){
        bool flag = (r > e) || (l <= m && pt[l].y < pt[r].y);
        int  &idx = flag ? l : r;
        deque<int> &from = flag ? v : u;
        deque<int> &  to = flag ? u : v;

        while(from.size() && pt[idx].y-pt[from[0]].y > k) from.pop_front();
        if(from.size() && abs(pt[from[0]].x - pt[idx].x) <= k) uf.merge(pt[from[0]].i, pt[idx].i);
        while(to.size()){
            if(abs(pt[to.back()].x - x_m) > abs(pt[idx].x - x_m)) to.pop_back();
            else break;
        }
        to.push_back(idx);
        tmp[pv++] = pt[idx++];
    }
    for(int i=s; i<=e; i++) pt[i] = tmp[i];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k; uf.init(n);
    for(int i=1; i<=n; i++){
        int x, y; cin >> x >> y;
        pt[i] = {x+y, x-y, i};
    }
    sort(pt+1, pt+n+1);
    f(1, n);
    cout << uf.cnt << " " << uf.get_max();
}