BOJ 16074 Mountaineers (병렬 이분 탐색)

https://www.acmicpc.net/problem/16074

16074번: Mountaineers

지형이 주어지고, 어느 두 지점을 이동하는 경로 중 경로상 최고 고도를 최소화하는 문제이다.

쿼리의 개수가 5만개 이므로, 각 쿼리에 대해 BFS를 하는 등의 전략을 취할 수 없다.

우선 지도를 그래프로 모델링 한다. 좌표상 한 지점을 정점으로 보고, 동서남북 연결 경로를 간선으로 볼 수 있다. 전체 정점수 V는 최대 500*500개, 최대 간선수 E는 정점수 V의 약 4배이다. 간선의 가중치는 간선이 연결하는 두 지점 a와 b 중 높은 고도로 한다.

방법 1 - Parallel Binary Search (PBS)

문제를 결정문제로 바꿔서 생각해 볼 수 있다. 우선 최대 높이 h를 설정하고, 높이가 h이상인 지점을 통과하지 않으면서 쿼리상 주어진 두 지점을 연결할 수 있는지 보는 방법이 있다.

하나의 쿼리에 대해서 결정문제를 푸는 방법:

1. 분리 집합(union-find)을 초기화한다.
2. 간선중 높이가 h이하인 모든 간선에 대해 간선의 양 끝 정점을 같은 집합에 넣는다.
3. 쿼리에 주어진 두 정점이 같은 집합에 포함되어 있는지 본다.
   1. 같은 집합이면, 두 정점은 높이가 h이하인 지점만 이용하여 연결할 수 있다.
   2. 같은 집합이 아니면, 두 정점을 연결하기 위해서 높이가 h보다 큰 지점을 통과해야 한다.

최소 높이 h를 구하기 위해서 이분 탐색을 할 수 있다.  시간복잡도는 O(V log V * log H) (H=최대고도) 이다.

모든 쿼리에 대해서 개별로 이분 탐색을 하면 전체 시간복잡도는 (QV log V * log H)이므로 너무 오래 걸린다.

모든 쿼리에 대해서 개별로 이분탐색을 하는 과정을 보면, 예를 들어 h=5인 결정 문제와 h=9인 결정 문제를 풀어야 한다고 하자. 두 결정문제 모두 가중치가 5이하인 간선을 이용하여 분리집합을 구성하는 과정이 있다. 즉 h=5인 결정문제를 푸는 과정에서 만들어진 분리집합을 h=9인 결정문제를 푸는데에 재활용하면, Kruskal알고리즘을 매번 새로 시작하지 않고 한 번에 모든 쿼리에 대한 결정문제를 풀 수 있다.

각 쿼리에 대해서, 현 단계에서 풀어야 하는 결정 문제의 파라메터 lower_bound, upper_bound를 유지한다. Kruskal을 수행하면서 모든 mid=(lower_bound+upper_bound)/2 에 대해,  mid보다 가중치가 작은 간선만을 이용하여 분리집합을 구성한다. mid에 해당하는 쿼리를 수행한 뒤 결과에 따라 파라메터를 수정한다. (lower_bound = mid + 1 or upper_bound = mid - 1)

vector<ans_t> Solve(int no_answer = -1) {
    for (int i = 0; i < as.size(); ++i) as[i] = no_answer;

    while (true) {
        bool solved = true;
        map<idx_t, vector<int>> qm;
        for (int qi = 0; qi < qs.size(); ++qi) {
            int lb = lbs[qi];
            int ub = ubs[qi];
            if (lb <= ub) {
                solved = false;
                int mid = (lb + ub) / 2;
                qm[mid].push_back(qi);
            }
        }
        if (solved) break;

        dm->Init();

        for (auto& [tidx, qis]: qm) {
            dm->PrepareTo(tidx);
            for (auto qi: qis) {
                auto& q = qs[qi];
                if (dm->Decide(q)) {
                    as[qi] = tidx;
                    ubs[qi] = tidx - 1;
                } else {
                    lbs[qi] = tidx + 1;
                }
            }
        }
    }
    return as;
}

쿼리를 해결하기 위해 결정 문제를 풀어야 하는 횟수는 O(log H)이고, Kruskal알고리즘을 한 번 수행하여 전체 쿼리에 대해 결정문제를 1회 해결할 수 있으므로, 전체 시간복잡도는 O((Q+V)log V * log H)이다.

방법 2- Heavy-Light Decomposition

주어진 그래프의 최소 신장 트리를 찾는다. 최소 신장 트리에서 아무 노드나 하나 골라서 그 노드를 root로 하는 트리를 만든다. 이 트리에 대해 HLD을 적용한다.

하나의 쿼리에 대해 두 정점 a, b의 LCA p를 찾으면, a와 b를 연결하는 경로중 최대 고도를 최소로 하는 고도는 a->p->b상 최대 가중치와 같다.

시간 복잡도 = O((Q+V)logV)

비교

• 구현량: HLD자체가 구현량이 꽤 많기 때문에, 스크래치부터 구현하자면 방법 1이 구현량이 더 적다.
• 해법 난이도: 방법 1이 더 직관적으로 느껴지고, 처음 문제를 보았을 때 가장 먼저 떠오른 해법도 방법 1에 가까웠다.
• 구현 시간:
  • 잘 갖추어진 HLD 라이브러리가 있다면, 방법 2가 구현 시간이 더 짧을 것이다.
    • PBS는 미리 라이브러리를 만들어 두기가 까다롭다.
  • HLD라이브러리가 없다면, 방법 1이 구현 시간이 더 짧을 것이다.
    • HLD는 구현량도 많고, 버그 없이 구현하기 매우 까다롭다.
• 시간복잡도: HLD 방법이 더 효율적일 것으로 예상된다. 
  • 실제로 HLD코드가 약 2배 정도 더 빨랐다.

• 이외의 방법
  • 분리집합을 확장하여, 두 정점 a, b를 하나의 집합으로 통합하게만든 간선을 역추적하는 방법을 생각할 수 있다. 시간복잡도는 O((V + Q) logV) 정도가 될 것 같다.