거울대칭트리 그래프 (BOJ 2430. BOI 2011)

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

쉽게 가자. 만약에 두 트리의 루트 T1, T2가 주어졌다면 어떨까?

* 1. T1과 T2에서 BFS를 돌린다.

* 2. 그래프에 모든 에지들을 T1쪽에 속하는지, T2쪽에 속하는지 분류하는 방법을 알려주자면, i - j를 잇는 에지에 대해서 (D(T1, i) + D(T1, j)) / 2와 ((D(T2, i) + D(T2, j)) / 2를 생각해보자. (무게 중심) 두 값중 작은 쪽이 존재한다면, 그 쪽에 속하는 에지로 보내버리고, 만약에 두 값이 같다면 이건 거울대칭트리 그래프가 아니다. 이렇게 하면 두개의 트리가 만들어 진다. 트리가 아닌 다른 게 만들어졌다면 (E != V-1) NO 찍자.

* 3. 리프 번호가 같고, 트리의 구성 에지가 같은지를 체크하는 것이 목표이다. Tree Isomorphism이라고 불리는 문제인데, 경시 대회에서 쓰기 가장 좋은 방법은 해싱이라고 생각한다. 깊이 차를 충돌 없이 잘 표현하며, 서브트리의 rotation에 상관 없는 표기법을 잘 사용하면(...) 풀 수 있다. 리프일때는 노드 인덱스를 반환하는 걸 잊지 말아야 함.

트리 의 루트 T1, T2의 경우의 수가 O(N^2)니 이렇게 O(N^2M) 알고리즘을 만들 수 있다. (사실 해싱 쓰는 tree isomorphism이 O(NlgN)이긴 한데.. 저 문제는 해싱 없이 O(N)에 풀린다고 하니 이 부분은 넘어가자.) 이제 문제는 T1과 T2를 구하는 쪽으로 넘어갔다.

T1과 T2를 구하는 방법을 조금 쉬운 걸 찾으려고 했지만 그런게 잘 나오진 않았다. 나는 두개의 사이클을 활용했다. 임의의 degree가 3인 점을 잡고, 이 점을 지나는 두개의 사이클을 구하자. (인접한 두개의 간선을 block하고 bfs를 돌리면 쉽게 구할 수 있다.) 그러한 점이 없거나 그러한 점에서 사이클이 안 생길 수 있는데 이건 나중에 설명.

두 사이클이 공통으로 겹치는 경로를 구한다. 경로의 정확한 중점이 존재한다면 찍자. 이 중점은 두 트리의 리프이다. 리프인 고로 degree가 2고, 양옆에 있는 정점을 루트로 잡으면 된다. 이 문단에서 뭔가 안되는 부분이 존재한다면 NO를 찍으면 된다.

이제 두개의 케이스를 설명한다.

* 1. degree가 3인 점을 잡았는데 사이클이 안 생겼다 -> 루트가 리프인 경우가 아니다. 루트가 리프가 아니면 절대 저런 일은 일어나지 않는다. 루틴이 돌기 전에 그래프 전체에서 degree가 1인 점 두개를 찾자. 1개나 3개 이상이면 NO, 2개면 그 두개의 점이 루트일 것이다. 0개면 위에 적힌 루틴을 돌린다.

* 2. degree가 3인 점이 없다 -> 원본 트리에서 degree가 3인 점이 없었다는 뜻이다. 트리가 일직선인 경우인데, 루트가 일직선의 끝에 있었다면 1번에 의해서 걸러지고, 루트가 일직선 중간에 있었다면 이 그래프는 사이클 하나로만 이루어진 그래프이다. 일단 그런 경우인지 보고, 그런 경우라면 n의 홀짝에 따라 답이 결정된다.

cpp : https://github.com/koosaga/olympiad/blob/master/BOI/boi11_treemirror.cpp 대략 4000byte 정도 나왔다. 코드는 맘먹고 짜면 의외로 짤만하다.

5 시간 안에 풀 문제는 아니라 생각하는데 대회 당시에 두명이나 만점자가 있었다고 한다. 풀 피드백 시절도 아닌데 대단. http://web.archive.org/web/20110509070820/http://boi2011.dk/index.php/results 이 문제를 풀면서 비슷하다고 느낀 문제는 IOI 2012 Rings였다. 생각을 겁나 하면 답이 나오기는 하는데 어떻게 잘 깔끔하게 생각하느냐가 핵심인 문제.. (난 한참 생각했는데 대회 때 푼 사람들이 많다는 것도 비슷하다)