반응형
SMALL
백준 11437 python
-
백준 11437번 LCA , 11438번 LCA2알고리즘 2023. 8. 2. 12:21
LCA란 Lowest Common Ancestor로 두 정점의 가장 가까운 공통 조상을 찾는 문제입니다 시도 1. 루트 노드인 1번 노드부터 연결된 간선을 통해 자식 노드들을 내려가게 됩니다. 이 때, 자식노드의 부모노드를 모두 저장하면서 내려가도록 합니다. 여기서 중요한 것은 주어지는 입력이 루트노드로부터 가까운 순이 아니므로, 모든 간선의 입력을 받은 뒤 부모노드와 자식 노드를 분간해야 된다는 것입니다. 모든 노드의 부모노드를 찾은 뒤, 두 정점으로부터 가까운 공통 부모를 찾아줍니다. 한 노드로부터 부모노드로 계속 이동하여 루트 노드까지 방문하고 방문한 노드에 표시를 해줍니다(visited 배열을 통해). 그 다음 다른 노드 또한 부모노드로 계속 이동하여 루트 노드까지 이동하는데 visited 배열에..