BOJ 16307 Driver Disagreement

문제 링크입니다.

느린 풀이 생각하기

앨리스와 밥이 주장하는 현재 위치의 쌍 $(A, B)$를 정점으로 두고 BFS를 돌리고 싶은 세팅입니다. 그렇지만… 그냥 BFS를 돌리면 금방이라도 시간 초과가 날 것만 같은 제한입니다.

솔직히 BFS보다 나은 풀이 전략이 딱히 없는 유형의 문제입니다. 현재 정점의 개수는 $\mathcal{O}(N^2)$개 정도고, 간선은 한 정점 당 두 개이므로 정점의 개수에 비례합니다. 그러니, 시간 복잡도의 개선을 위해 정점의 개수를 깎아내 볼 겁니다.

관찰

어떤 종류의 정점은 탐색해 볼 필요도 없습니다. 예를 들어, $(0, 0)$과 같은 쌍은 두 사람이 실제로 같은 위치를 생각하고 있으니 당연히 두 위치를 구분할 수 없습니다.

이렇게 탐색할 필요가 없는 정점의 수를 늘리면 우리가 BFS를 돌면서 실제로 확인해야 하는 정점의 수는 줄어들 겁니다. 이를 위해 사실상 같은 위치의 개념을 도입합시다.

$(A, B)$가 사실상 같은 위치려면,

• $A = B$이거나,
• $(L_A, L_B)$와 $(R_A, R_B)$가 각각 사실상 같은 위치여야 합니다.

사실상 같은 위치에서 이동을 시작했다면, 궁극적으로 $(X, X)$와 같이 두 위치가 서로 같은 쌍으로 보내지거나 사실상 같은 위치의 정점들 안에서만 뱅뱅 돌게 됩니다. 그렇다는 것은 사실상 같은 위치에서 시작한 이동 과정 중에 만나는 모든 정점 $(X, Y)$가 $t_X = t_Y$를 만족함을 뜻합니다.

이제 $(A, B)$와 $(B, C)$가 각각 사실상 서로 같은 위치라고 생각합시다. 그러면, 임의의 동일한 이동을 해서 $A, B, C$를 각각 $X, Y, Z$로 보냈을 때 $t_X = t_Y$이고 $t_Y = t_Z$입니다. 따라서 $t_X = t_Z$가 성립하고, 이것이 모든 이동에 대해 성립하므로 $(A, C)$ 역시 사실상 같은 위치입니다.

추이성을 이용한 최적화

BFS의 작동 과정을 들여다 봅시다. 만약 우리가 $(A, B)$와 $(B, C)$에 각각 방문한 후에 $(A, C)$를 방문한다면…

• 최종적으로 $(A, B)$와 $(B, C)$가 모두 사실상 같은 위치로 판명 난다면 $(A, C)$ 또한 사실상 같은 위치입니다. 이 경우에는 $(A, C)$를 굳이 탐색해 볼 필요가 없습니다.
• 그 대우로서, $(A, C)$에서 어떤 이동을 통해 즉시 구별 가능한 두 위치의 쌍 $(X, Z)$에 도달할 수 있다면, $(A, B)$나 $(B, C)$ 중 적어도 하나 또한 적당한 이동을 통해 어떤 구별 가능한 위치의 쌍에 도달할 수 있습니다. 하지만 얼마나 빨리 도달할 수 있을까요?
  • $(A, C)$에서 $(X, Z)$에 도달하기 위한 이동의 리스트를 $Q$라고 합시다. 이 $Q$를 그대로 $(A, B)$와 $(B, C)$에 먹이면 각각 $(X, Y)$와 $(Y, Z)$로 이동하게 됩니다. 가정에 따라 $t_X \neq t_Z$이고, $t_Y$는 0 또는 1이므로, $(X, Y)$와 $(Y, Z)$ 중 적어도 하나는 즉시 구별 가능한 위치의 쌍입니다.
  • 동일한 길이의 이동으로 $(A, B)$와 $(A, C)$가 모두 직접 구별 가능한 위치의 쌍으로 이동 가능하다면, 우리가 BFS 상에서 먼저 탐색을 시작한 $(A, B)$ 쪽이 시작 정점으로부터의 거리가 더 짧기 때문에 항상 $(A, C)$를 탐색하는 것보다 유리합니다.

따라서, $(A, B)$와 $(B, C)$를 모두 방문했다면 $(A, C)$를 방문할 필요가 없습니다.

이 점을 이용해, 어떤 정점 $(A, B)$를 방문했다면 $A$와 $B$를 분리 집합 등의 자료 구조를 이용해 하나의 그룹으로 묶어줄 수 있습니다. 이렇게 하면 이미 같은 그룹에 속한 두 수의 쌍을 방문하지 않고 넘길 수 있습니다. 그리고 그러한 쌍의 수는 많아봤자 $\mathcal{O}(N)$개이므로, 우리는 전체 문제를 거의 $\mathcal{O}(N)$에 해결할 수 있습니다!

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int par[101010], l[101010], r[101010], vis[101010];

int f(int x){return par[x] < 0 ? x : par[x] = f(par[x]);}
bool u(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return 1;
	if(par[x] > par[y]) swap(x, y);
	par[x] += par[y];
	par[y] = x;
	return 0;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	memset(par, -1, sizeof(par));
	int n, A, B; cin >> n >> A >> B;
	for(int i = 0; i < n; i++) cin >> l[i] >> r[i] >> vis[i];
	queue<tuple<int,int,int>> q; q.push({A, B, 0});
	while(q.size()){
		auto [a, b, d] = q.front(); q.pop();
		if(u(a, b)) continue;
		if(vis[a] != vis[b]) return !(cout << d);
		q.push({l[a], l[b], d+1});
		q.push({r[a], r[b], d+1});	
	}
	cout << "indistinguishable";
}