가까운 공통 조상 찾기 > 문제은행

본문 바로가기


실전대비 Level5

1440 : 가까운 공통 조상 찾기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 112 회    시도횟수: 352 회   



루트가 있는 트리는 컴퓨터 과학이나 엔지니어링에서 잘 알려진 자료구조이다. 예를 들면 다음과 같다.

 

e3050b66a1b29a01767400d7560a4131_1449745
 

위 그림에서 각각의 노드는 {1,2,...,16}의 라벨을 1개씩 가지고 있다. 8번 노드는 루트이다. 만약 노드 x가 루트에서부터 노드 y까지의 경로(path) 상에 나타나면 x는 노드 y의 조상이 된다. 이를 테면 노드 4는 노드 16의 조상입니다. 노드 10 역시 노드 16의 조상이다.

노드 x가 서로 다른 노드 y와 z의 조상이면 x를 y와 z의 공통 조상이라고 부른다. 이러한 공통 조상들 중에 y와 z에 가장 가까운 공통 조상을 가장 가까운 공통 조상이라고 칭한다. 따라서 2와 3의 가장 가까운 공통 조상은 10이 된다. 만약 y가 z의 조상이라면 y가 가장 가까운 공통 조상이 된다.

트리 내에서 두 개의 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하라.


첫 줄에 노드의 수 N 2≤N≤10,000 이 주어지고 N-1줄에 걸쳐 두 개의 정수가 주어진다.
두 수 중 첫 번째 수가 두 번째 수의 부모 노드가 된다.
다음으로 2개의 서로 다른 정수가 주어지는데 가장 가까운 공통 조상을 알고 싶은 두 개의 노드이다.


두 개의 노드에 대한 가장 가까운 공통 조상의 번호를 출력한다.

[Copy]
16 
1 14 
8 5 
10 16 
5 9 
4 6 
8 4 
4 10 
1 13 
6 15 
10 11 
6 7 
10 2 
16 3 
8 1 
16 12 
16 7
[Copy]
4


출처 : Taejon 2002


Taejon 2002 poj1330

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.