BOJ/백준-3584-python

문제📖

풀이🙏

• 첫 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어진다. (2 <= N <= 10000)
• N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B가 주어지는데, 이는 A가 B의 부모라는 뜻입니다.
• 테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어진다.
• 각 테스트 케이스 별로, 첫 줄에 입력해서 주어진 두 노드의 가장 가까운 공통 조상을 출력하라.
  -> LCA 알고리즘 문제이다.
  -> lca 알고리즘을 이용하여 풀었지만 시간초과가 계속나서 아래 링크의 글을 참고하여 풀었다.
  개발일기님 블로그

코드💻

# boj, 3584: 가장 가까운 공통 조상,python3
import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N=int(sys.stdin.readline())
    p_list=[0 for _ in range(N+1)]      #각 노드의 부모노드 저장
    for _ in range(N-1):
        p,c=map(int,sys.stdin.readline().split())
        p_list[c]=p                     #부모 노드 저장
 
    a,b=map(int,sys.stdin.readline().split())
    
    a_parent=[a]
    b_parent=[b]
                                        #각노드의 부모노드가 루트일때까지 모두 저장
    while p_list[a]:
        a_parent.append(p_list[a])
        a=p_list[a]
 
    while p_list[b]:
        b_parent.append(p_list[b])
        b=p_list[b]
 
                                        #같은 레벨로 맞추고 부모노드 같은거 찾기
 
    a_level=len(a_parent)-1
    b_level=len(b_parent)-1
                                        # 루트노드부터 차례대로 비교
    while a_parent[a_level]==b_parent[b_level]:   #부모노드가 같지 않을때까지
        a_level-=1
        b_level-=1
 
    print(a_parent[a_level+1])

결과😎

출처 && 깃허브📝

https://www.acmicpc.net/problem/3584
github