Baltic OI 2011 Tree Mirroring

BOJ 2430 : 거울대칭트리 그래프.

주어진 그래프가 거울대칭트리 그래프면 만족해야 하는 충분조건들을 생각해보자.

Case 1 : 복사 전의 루트가 degree 1인 경우

결과 그래프에는 반드시 degree가 1인 정점이 두 개 존재해야 한다. 그 두 정점을 기준으로 그래프가 대칭적이어야 하고, 그 중심에는 모든 leaf들이 있어야 할 것이다. 즉 그 두 정점을 a와 b라고 하고, a를 기준으로 BFS한 거리 배열을 d1, b를 기준으로 한 BFS 거리 배열을 d2라고 했을 때, d1[i]<=d2[i]인 점들의 집합은 a를 기준으로 한 rooted tree를 이루고, d1[i]>=d2[i]인 점들의 집합은 b를 기준으로 한 rooted tree를 이루며, 그 두 rooted 트리가 같은 모양이어야 한다.

Case 2 : 복사 전의 루트가 degree 2 이상인 경우

결과 그래프는 degree가 1인 정점이 없어야 한다. 또한 크기 4 이상의 사이클이 존재하며, 모든 사이클의 크기는 짝수여야 한다. 임의의 사이클 C를 잡아보자. 전체 그래프가 C뿐이라면, 답은 항상 YES일 것이다. 그렇지 않다면 C와 연결된 정점이 최소한 하나는 있다. C 위에 있는 점 a에서 C 밖에 있는 점 x와 연결되어있다고 하자.

a는 원래 트리에서 leaf가 아니다. (leaf는 degree가 2 뿐으로, 양쪽이 사이클의 점을 잡고 있을 수밖에 없다.) 원래 트리에서 x는 a의 자식이거나 부모였다.

자식이었다면

x에서 자식으로 내려가다 보면 반대편 트리로 넘어가서 다시 a에 해당하는 반대편 점을 만난다. 그럼 사이클의 특성 상 그런 점 또한 C 위에 있을 것이므로 C를 만나게 되어있는 모양이다.

부모였다면

부모쪽으로 거슬러 올라가다 보면 반드시 a쪽이 아닌 새로운 자식이 나올 것이다. 그쪽으로 쭉 내려가서 반대편 점으로 간 다음, 그쪽의 a에 해당하는 점으로 간다면 역시 C와 만난다.

위의 두 경우 모두, 항상 x에서 C의 다른 점 b를 향하는 경로가 최소한 하나가 있다. 잘 생각해보면 x에서 DFS를 돌렸다면 가장 먼저 만나는 b는 a의 대칭적인 위치에 있는 점이다.

조금 더 잘 생각해보면, 대칭을 시킬 때 루트가 어디였는가는 별로 중요하지 않다. root의 degree는 2 이상이므로, leaf가 아닌 임의의 새로운 점을 root로 잡아본다면? 거울대칭트리를 만들면 정확히 같은 그래프가 나온다. 그러면 거꾸로 a와 b를 각각 root로 생각해도 되는 것!

이제 처음에 degree가 1인 것에서 했던 것처럼 a와 b에서 BFS를 돌린 후 각각의 트리를 비교해보자. 여기서 논리를 뒤집을 수 있다. 우리는 '거울대칭그래프이다'가 가정일 때의 성질들에 대해서 생각했다. 즉 a와 b를 root로 생각했을 때 조건을 만족하지 않는다면, 주어진 그래프는 거울대칭그래프가 아니다. 그런데 이제는 조건을 만족한다면 거울대칭그래프라는 주장을 할 수 있어, 논리가 완성된다.

결론

degree가 1인 점이 있는가?

YES -> 반드시 두 개 있어야 하며, 각각을 루트로 잡아서 d_me[x] >= d_other[x]인 점들을 가지고 만든 트리가 같아야한다. NO -> 사이클을 찾고, 사이클과 인접해있는 사이클 외부의 점에서 또다른 경로를 찾아 두 개의 점을 찾는다. 각각을 루트로 한 트리가 같은지 확인한다.

근데 왜 틀리지...