[Algorithm] cpp 백준 16074번: Mountaineers

문제

링크: https://www.acmicpc.net/problem/16074
요약: m×n 격자에서 상하좌우로만 이동할 수 있고, 각 칸에는 고도가 주어집니다. (x1,y1)에서 (x2,y2)로 이동하려면 경로 상에서 마주치는 칸들의 고도 중 최대값이 최소가 되도록 해야 합니다. 각 질의마다 이 최소 가능한 최대 고도를 출력합니다.

입력/출력

1
2
3
4
5
6
7
8
9
<입력>
m n q
height[1][1..n]
...
height[m][1..n]
q개의 줄: x1 y1 x2 y2

<출력>
각 질의에 대한 최소 가능한 최대 고도(정수)

예시

접근 개요

핵심 관찰: 원하는 값은 경로 상의 최대 고도를 최소화한 값(최소-최대, minimax)입니다. 이는 그래프에서 간선 가중치를 max(h[u], h[v])로 정의했을 때의 병목(bottleneck) 경로 최소화와 동치이며, MST에서 두 정점 사이 경로의 최대 간선 가중치로 계산할 수 있습니다.
전략: 격자 그래프의 모든 칸을 높이 오름차순으로 활성화하면서, 이미 활성화된 인접 칸과만 연결하는 Kruskal 스타일의 유니온파인드로 MST를 구성합니다. 간선 가중치는 max(h[u], h[v])를 사용합니다.
질의 처리: 구성된 MST 위에서 LCA(이진 리프팅)를 준비하여, 두 정점 경로의 최대 간선 가중치를 O(log V)에 구합니다. 같은 칸일 때는 그 칸의 높이가 답입니다.

알고리즘

그래프 구성 및 MST

정점: 각 칸 (i,j) → id = i·n + j
간선: 상하좌우 인접 쌍 (u,v), 가중치 w = max(h[u], h[v])
구현: 칸들을 높이 오름차순으로 활성화. 새로 활성화된 칸 u에 대해, 이미 활성화된 인접 v와만 unite(u,v) 수행. unite가 성공할 때만 간선을 MST에 채택하고 가중치를 기록.

LCA 준비(이진 리프팅)

MST는 트리이므로 임의 루트에서 BFS로 깊이와 1번 조상을 채웁니다.
up[v][k] = v의 2^k번째 조상, mx[v][k] = 루트 방향으로 2^k만큼 올릴 때 거치는 간선들의 최대값.

질의(u,v) 처리

깊이를 맞추며 올라가며 최대값을 갱신.
공통 조상 직전까지 동시에 점프하며 최대값을 갱신.
마지막으로 부모 간선 2개를 반영해 답을 얻음. u==v면 0이 나오므로 max(0, h[u], h[v])로 보정.

올바름 근거(요지)

Kruskal의 컷 성질: 간선 가중치가 max(h[u],h[v])인 그래프의 MST에서 두 점 사이 경로의 최대 간선 가중치는 원 그래프에서 가능한 경로들 중 최소의 병목값과 같습니다. 따라서 LCA로 얻는 최대 간선값이 곧 요구하는 최소-최대 고도입니다.
활성화 방식은 모든 간선을 가중치 오름차순으로 본 것과 동치이며, unite 시에만 간선을 채택하므로 정확히 MST를 생성합니다.

복잡도

V = m·n, E ≈ 2mn. 정렬 O(V log V). 유니온파인드로 MST 구성 O(E α(V)).
LCA 전처리 O(V log V), 질의당 O(log V). 전체 O(V log V + E α(V) + q log V).

구현 (C++)

  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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, compSize;
    DSU(int n) : parent(n), compSize(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (compSize[a] < compSize[b]) swap(a, b);
        parent[b] = a;
        compSize[a] += compSize[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n, q;
    if (!(cin >> m >> n >> q)) return 0;
    const int N = m * n;

    vector<int> height(N);
    vector<pair<int,int>> cells; cells.reserve(N);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int h; cin >> h;
            int id = i * n + j;
            height[id] = h;
            cells.emplace_back(h, id);
        }
    }

    vector<pair<int,int>> query_pairs(q);
    for (int i = 0; i < q; ++i) {
        int x1, y1, x2, y2; 
        cin >> x1 >> y1 >> x2 >> y2;
        --x1; --y1; --x2; --y2;
        query_pairs[i] = {x1 * n + y1, x2 * n + y2};
    }

    sort(cells.begin(), cells.end()); // by height asc

    DSU dsu(N);
    vector<char> active(N, 0);
    vector<vector<pair<int,int>>> adj(N);
    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};

    for (auto &p : cells) {
        int id = p.second;
        int r = id / n, c = id % n;
        active[id] = 1;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int nid = nr * n + nc;
            if (!active[nid]) continue;
            int w = max(height[id], height[nid]);
            if (dsu.unite(id, nid)) {
                adj[id].push_back({nid, w});
                adj[nid].push_back({id, w});
            }
        }
    }

    const int LOG = 20;
    vector<int> depth(N, -1);
    vector<array<int,LOG>> up(N);
    vector<array<int,LOG>> mx(N);
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < LOG; ++k) {
            up[i][k] = -1;
            mx[i][k] = 0;
        }
    }

    // BFS to set depth and 1st ancestors
    queue<int> qu;
    int root = 0;
    depth[root] = 0;
    qu.push(root);
    while (!qu.empty()) {
        int u = qu.front(); qu.pop();
        for (auto &e : adj[u]) {
            int v = e.first, w = e.second;
            if (depth[v] != -1) continue;
            depth[v] = depth[u] + 1;
            up[v][0] = u;
            mx[v][0] = w;
            qu.push(v);
        }
    }

    // Binary lifting tables
    for (int k = 1; k < LOG; ++k) {
        for (int v = 0; v < N; ++v) {
            if (up[v][0] == -1) continue;
            int mid = up[v][k - 1];
            if (mid == -1) continue;
            up[v][k] = up[mid][k - 1];
            mx[v][k] = max(mx[v][k - 1], mx[mid][k - 1]);
        }
    }

    auto maxOnPath = [&](int u, int v) {
        if (u == v) return 0;
        int ans = 0;
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; ++k) {
            if (diff & (1 << k)) {
                ans = max(ans, mx[u][k]);
                u = up[u][k];
            }
        }
        if (u == v) return ans;
        for (int k = LOG - 1; k >= 0; --k) {
            if (up[u][k] != -1 && up[u][k] != up[v][k]) {
                ans = max(ans, mx[u][k]);
                ans = max(ans, mx[v][k]);
                u = up[u][k];
                v = up[v][k];
            }
        }
        ans = max(ans, mx[u][0]);
        ans = max(ans, mx[v][0]);
        return ans;
    };

    ostringstream out;
    for (int i = 0; i < q; ++i) {
        int s = query_pairs[i].first, t = query_pairs[i].second;
        int bottleneck = maxOnPath(s, t);
        int ans = max(bottleneck, max(height[s], height[t]));
        out << ans << '\n';
    }
    cout << out.str();
    return 0;
}