백준 20349번 Xortest Path

문제 요약

정점 수가 $n$이고 간선 수가 $m$인 그래프가 주어진다. 어떤 경로의 거리는 해당 결로에 속하는 간선들의 XOR로 정의한다. 이 때, 쿼리가 $q$개 주어지는데 두 정점의 번호가 주어진다. 두 정점간의 경로 중에서 최단거리를 가지는 경로의 거리를 출력하시오.

$ 1 \le n \le 10^4 $, $ n-1 \le m \le 10^5$, $ 1 \le q \le 10^5$, 각 간선의 가중치는 최대 $10^{18}$이다.

풀이

두 정점이 주어지면 두 정점간의 최단 경로를 찾아야 한다. 일반적으로 그래프에서 이는 매우 어렵다. 그런데 이런 문제를 냈다는 것은 XOR로 정의한 새로운 거리가 무슨 특성을 갖고 있기에 냈을 것이다.

일단 그래프가 connected라는 조건을 줬으니 트리에서 생각을 해보자. 트리였다면 하나의 정점을 루트로 잡고 각 정점마다 루트로부터의 거리를 저장한 뒤에 LCA를 구해서 처리하면 될 것이다. 왜냐면 경로는 유일하니까!

그래프는 뭐가 다르길래 트리보다 어려울까? 트리에서 간선 하나만 추가되어도 사이클이 생기고 경로가 유일하지 않으며 골치가 아파진다. 그런데 만약 사이클이 생겼다면 그 사이클은 어떤 역할을 할까?

어떤 경로가 있다고 치자. 해당 경로 상에 있는 정점 중 어느것이라도 사이클에 속하는 게 있다면 그 사이클을 들러서 경로 상의 거리를 바꿔줌과 동시에 경로의 출발지와 목적지는 변하게 하지 않을 수 있다.

그리고 경로의 거리가 바뀌는 부분은 정확히 사이클의 거리만큼을 XOR 해준것과 동일하다. 그렇다면 만약에 각 비트별로 1씩을 가지는 사이클이 존재하고 모든 경로가 그 사이클에 속하는 정점을 가지게 한다면, 각 비트를 지워줄 수 있지 않을까?

이런 아이디어를 생각해냈다면 거의 다 온 것이다. 먼저, 쿼리를 처리하기 위한 모든 경로가 사이클에 속하는 정점을 가지게 하는 것은 간단하다. 그냥 DFS 트리를 만들고 쿼리로 주어지는 $a, b$의 경로는 루트를 지나간다고 생각하면 된다.

그리고 비슷한 방식으로 모든 사이클이 루트를 지나도록 하면 된다. 그러한 모든 사이클을 찾는 것은 back edge를 찾을 때마다 그러한 사이클로 생각하면 된다.

이제 $i$번째 비트만 켜진 사이클은 어떻게 만들어야 할까? 사이클도 하나의 경로로 본다면 사이클끼리도 서로를 지워줄 수 있다. 이를 통해 모든 사이클로 최대한 $i$번째 비트만 남길 수 있도록 하고자 한다.

이는 가우스 소거법과 동일한 과정을 통해 진행하면 된다. 가우스 소거법은 $O(n^3)$아니었나? 아니다. 정확히는 $O(nm^2)$이다. 여기서 $m$은 간선 수가 아니라 열(column)의 수다.

그래서 사이클들을 전부 모아서 가우스 소거법을 진행해주고 basis(기저)를 얻어낸 뒤에 쿼리로 $(a, b)$가 들어오면 $a \rightarrow root \rightarrow b$ 경로의 거리를 구한 뒤에 basis로 지울 수 있는 비트들을 지워나가면 그게 최단 거리가 된다.

지난번에 팀연습하고 솔루션 깠을 땐 전혀 이해를 못했는데 오늘 지하철에서 이해가 됐다. 다행이다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e4;
vector<vector<pair<int, ll>>> G(MAXN+1);
vector<ll> dist(MAXN+1, -1);
vector<ll> rows;
int N, M, Q;

void dfs(int cur, int par, ll val) {
    dist[cur] = val;
    for(pair<int, ll> p : G[cur]) {
        int nxt = p.first;
        ll w = p.second;
        if(nxt == par) continue;
        if(dist[nxt] == -1) dfs(nxt, cur, dist[cur]^w);
        else rows.push_back(dist[cur]^dist[nxt]^w);
    }
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    for(int i=0;i<M;++i) {
        ll u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    dfs(1, 0, 0);
    vector<ll> basis;
    if(!rows.empty()){
        sort(rows.begin(), rows.end());
        rows.erase(unique(rows.begin(), rows.end()), rows.end());
        while(basis.empty() || basis.back() != 0) {
            ll mx = *max_element(rows.begin(), rows.end());
            basis.push_back(mx);
            for(ll &v : rows) v = min(v, v^mx);
        }
    }
    for(int i=0;i<Q;++i) {
        ll u, v; cin >> u >> v;
        ll ans = dist[u]^dist[v];
        for(ll v : basis) ans = min(ans, ans^v);
        cout << ans << '\n';
    }
    return 0;
}