백준 114371 [백준 - Java] 11437번 : LCA 최소 공통 조상 문제 www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LinkedList를 통해 각 정점들을 저장하고 연결해준다. 인접 리스트로 구현된 트리를 DFS로 탐색한다. 탐색하면서 각 노드의 깊이와 부모 노드를 배열에 저장한다. 왜냐? 각 노드의 부모 노드 값을 저장해두면, 두 개의 노드가 어디에 있든 따라 올라가다 보면 최소 공통 조상을 찾을 수 있기 때문! 깊이를 맞추는 이유는 그게 비교하기 편함! (같은 깊이에서 시작해야 만나는 순간을 찾기가 쉬움) 정점.. 2021. 1. 4. 이전 1 다음 728x90 반응형