본문 바로가기

가장가까운공통조상2

[백준/C++] 11437, 11438. LCA 1,2 문제 https://www.acmicpc.net/problem/11437 -> LCA 1 https://www.acmicpc.net/problem/11438 -> LCA 2 주어진 두 노드에 대해 LCA(가장 가까운 공통 조상)을 구하면 되는 문제이다. 1번과 2번의 차이는 노드의 최대 갯수 및 시간 제한의 차이이다. LCA2가 훨씬 빡빡하다. 풀이 1. 11437 LCA1번 풀이 연결된 두 노드 a,b가 N-1개의 줄에 걸쳐서 입력되는데, a,b중에 어떤 노드가 부모노드인지는 입력 받을 때에는 알 수가 없다. 그래서 처음에는 연결리스트 형태로 저장했다가, 입력을 다 받은 후에 BFS를 통해 루트인 1부터 타고 들어가서 트리구조를 파악할 수 있도록 했다. (각 노드의 부모와, 깊이 저장) 그리고 LCA를.. 2021. 7. 27.

[백준/C++] 3584. 가장 가까운 공통조상 문제 https://www.acmicpc.net/problem/3584 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다. 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요 풀이 입력된.. 2021. 7. 6.

이전 1 다음

티스토리툴바