[파이썬] 백준 3584번 - 가장 가까운 공통 조상 풀이

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

티어: 골드 4

 

 

 

 

로직

먼저, 그래프의 정보를 가져오고 부모 노드가 없는 노드를 찾아 루트 노드를 구해줍니다.

dfs를 이용해 루트 노드부터 공통 조상을 찾고자 하는 두 노드까지의 경로를 구해줍니다.

 

경로가 A = [1, 3, 5, 4], B = [1, 3, 2] 와 같이 있다고 했을 때, index i를 0부터 증가시키며 A[i]와 B[i]의 값이 같은지 확인하고, 같다면 i += 1, 다르다면 A[i-1]의 값이 LCA가 됩니다.