트리. [11725]

[1. 문제 설명]

루트가 1인 트리가 입력으로 주어질 때,

각 노드의 부모노드를 구하도록 한다.

 

 

 

[2. 풀이 접근]

Tree 자료구조

특징)

A. 하나의 노드는 여러 개의 자식을 가질 수 있어도, 부모는 하나만 가질 수 있다.

=> 아래와 같은 형태는 트리가 아니다.

=> B, C, D 는 A 라는 하나의 노드를 부모로 갖지만,

=> E, F 는 여러개의 부모 노드를 갖는다.

=> 이로 인해 아래 성질을 만족하지 못한다.

 

B. 루트에서 어떤 노드로 가는 경로는 유일하다.

=> 임의의 두 노드 간의 경로도 유일 하다

=> 두 개의 정점 사이에 반드시 1개의 경로만을 갖는다.

 

C. Root  노드는 다른 모든 노드들을 자손으로 갖는 노드로, Tree 에서 딱 하나 존재

D. Leaf 노드는 자식이 하나도 없는 노드

 

E. Cycle 이 존재하지 않는 연결 그래프.

 

루트에서 시작하였으므로, 인접한 노드들은 루트의 자식이 된다.

이러한 특성이 모든 노드에 적용 되므로,

 

bfs 로 해결가능하다.

(또는, dfs 로 도 해결 가능하다.)

 

 

[3. 코드]