트리. [2533]

[1. 문제 설명]

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

---

[2. 풀이 접근]

문제 조건에서 주어지는 그래프는 트리 형태이다.

 

어떤 노드에서 인접한 모든 노드가 얼리 어답터일 때만, 이 노드 역시 얼리어답터가 될 수 있다.

• leaf 노드인 경우, 이 노드가 얼리어답터가 될 수 없다.
• 트리에서 노드는 최소 2개 이상이다.
• Left - Root - Right 인 구조에서, Left 를 얼리어답터로 선정한다면, Right 역시 얼리어답터로 해야한다.
  => Root 만 얼리어답터로 선정하는 것이 더 낫다.
  
  
• 그래서, Leaf 노드 역시 얼리어답터가 되려면, Leaf 에 유일하게 연결되는 Parent 가 얼리어답터가 되어야 한다.

Leaf 및 parent 를 얻기 위한 트리 구성

• 임의의 root 를 먼저 잡도록 한다.
• 이 때, 아무 노드나 root 로 잡아도 된다.
  => 트리의 밸런스는 깨질 수 있지만, 이렇게 선택해도 나머지 SubTree 에는 영향을 주지 않는다.
  => 보통 1번 노드를 root 로 선정한다.
  
  
• root 를 시작으로 각 sub-tree 의 크기를 재귀적으로 구한다.
• leaf 는 sub-tree 의 크기가 1 인 노드이다.

나머지는 코드 참조,

---

[3. 코드]