알고리즘 일지
BOJ 2430 - 거울대칭트리 그래프 본문
https://www.acmicpc.net/problem/2430
2430번: 거울대칭트리 그래프
첫째 줄에 N과 M이 주어진다. N은 정점의 개수 M은 간선의 개수이다. 그래프의 정점은 1부터 N까지 번호가 매겨져 있다. 다음 M개의 줄에는 x와 y가 주어진다. (x ≠ y, 1 ≤ x, y ≤ N) x와 y는 하나의 간
www.acmicpc.net
이걸 풀기 위해, 트리 동형을 공부하고 왔다.
Case 1 : degree가 1 인 정점이 존재 할 때
- 정점이 2개 이여만 한다
- 두 정점을 루트로 하는 트리를 만드며, BFS를 돌려, 동시에 접하는 정점까지 트리로 만든다.
- 동시에 접하지 않는다면, 틀린 그래프 이다.
- 두 트리가 동형인지 비교한다.
Case 2 : degree가 다 2이상일 때
- 그래프가 원형 사이클을 이루는지 확인한다.
- 사이클을 하나 구한다음, 속하지 않는 외부의 점에서 탐색을 시도 하여, 사이클에 접하는 사이클 내부의 점 두개을 구한다.
- 이때, 접하는 점은 2개 일 수 밖에 없다.
- 이 두개의 점은 대칭이라고 가정하고, BfS를 돌려 나머지 모든 리프노드를 구한다.
- 리프노드를 하나 루트로 잡고, 트리 두개를 만들어 동형인지 비교한다.
왜 틀림?