Jonyo Programming

[BOJ 11438(P5)리뷰] 트리에서 두개의 정점이 주어졌을 때, 두 정점의 최소공통조상을 찾아야 한다. 최소 공통조상 이란 두개의 노드가 만나게 되는 부모 노드 중 가장 가까운 것을 말한다. 아래의 과정을 통해 구할 수 있다. dfs를 통해 모든 정점의 깊이를 기록하며 이때 자신의 위에있는 부모노드의 번호를 저장한다. 두개의 정점을 입력받고, 두 정점의 깊이를 맞춘다. 같아진 깊이로부터 위로 올라간다. 이 때, 만약 서로 같은 노드를 만나게되면 그게 최소공통조상이다. LCA 문제는 위 과정을 코드로 구현하면 풀 수 있으나 이 문제는 이방법으로는 풀 수 없다. 왜냐하면, 노드의 개수와 명령의 개수가 최대 10만개이므로 만약 리프노드에서 루트노드까지 찾는과정을 반복해야 한다면 시간초과가 날 수밖에없다...