[BOJ] 23172 Equivalent Pipeline

문제 링크: [BOJ 23172](https://www.acmicpc.net/problem/23172)

문제 요약

정점이 $n$개인 가중치 있는 트리가 $d$개 있다. $vT(i,j)$를 $T$에서 $i$와 $j$를 잇는 최단경로 중 가중치의 최솟값이라고 하자. 만약 모든 $i$, $j$ 쌍에 대해 이 값이 같다면 두 트리는 동치이다. 동치 관계를 구하여라.

풀이

트리에서 가장 가중치가 작은 간선들을 생각해보자. 이 간선들을 제거하면, 트리가 여러 컴포넌트로 쪼개질 것이다. 이때 같은 컴포넌트에 있는 정점들끼리의 $vT(i,j)$ 값은 반드시 최소 가중치보다 크고, 다른 컴포넌트에 있는 정점들끼리의 값은 정확히 최소 가중치일 것이다.

따라서 두 트리가 동치이려면 최소 가중치 간선들을 기준으로 쪼갰을 때 컴포넌트 관계는 정확히 같아야 한다. 다시 말하면 트리 $A$에서 어떤 임의의 두 정점이 같은 컴포넌트에 속해 있다면 동형인 트리 $B$에서도 같은 컴포넌트에 속해 있어야 하고, 반대도 마찬가지라는 것이다.

그러면 이걸 쪼개가면서 컴포넌트가 일치하는지 확인해주면 되는데, 이건 너무 어렵다. 일반적으로 쪼개는 것 보다는 합치는 것이 쉬우므로, 문제를 모두 쪼개진 상태에서부터 역으로 풀어보자.

처음에는 모든 정점이 크기가 1인 상태일 것이다. 만약 여기서 가중치가 가장 큰 간선들을 추가한다면, 정점들이 서로 합쳐지게 된다. 이 때 두 트리가 동형이려면, 정점들이 모두 합쳐졌을 때 컴포넌트 관계가 같아야 한다. 이를 비교하는 방법을 생각해 보자. 일단 간선이 건드리지 않는 정점들에 대해서는 관계가 변하지 않으므로 고려할 필요가 없다. 건드리는 정점들에 대해서는, 컴포넌트가 여럿일 수 있으므로 각 정점이 어떤 컴포넌트에 속해있는지를 알아야 한다. 만약 컴포넌트의 번호를 컴포넌트를 구성하는 정점 번호의 최솟값으로 대표하게 한다면 Union Find에서 이를 간단하게 확인할 수 있다.

결론적으로, 가중치가 가장 큰 간선에 대해서 두 트리가 동형이려면 merge를 끝냈을 때 각 정점들의 대표가 모두 같아야 한다. 맨 처음에 대표는 모두 자기 자신이었으므로, 두 트리가 동일한지를 확인하려면 변화한 정점에 대해서만 확인하면 된다. 따라서 각 트리마다 건드려진 정점의 목록과 각 정점의 대표를 저장하자.

만약 이 목록이 모두 같다면, 이제 컴포넌트 안은 별로 관심이 없다. 따라서 컴포넌트를 묶어 정점 하나로 압축시키자. 그러면 더 작은 가중치 간선에 대해서도 재귀적으로 문제를 해결할 수 있다.

구현은 각 트리의 merge 과정을 canonical form으로 기록한다고 생각하면 편하다. (합칠 때 사용한 간선의 가중치, 건드려진 정점의 대표값, 건드려진 정점)을 모은 후 정렬해서 트리의 고유한 값으로 사용할 수 있다. 이를 map에 넣고 비교하거나, 해싱하면 된다.

소스코드

http://boj.kr/0b1089a65c564a878dac63c7ee438f4a