LCA Baekjoon 1761 정점들의 거리 2019. 4. 22. Link https://www.acmicpc.net/problem/1761 소스결과 6504 KB / 668 ms 언어 C++ 17 출처 Baekjoon 분류 LCA 설명 가중치가 있는 트리가 주어질 때 두 정점 사이의 가중치의 합을 출력한다. 기존 LCA문제에서 가중치가 추가된 LCA문제. 단지 루트 노드가 지정이 되지 않았기에 어느 노드를 기준으로 깊이를 설정해도 상관은 없다. 가장 일반적이게 1번 노드를 기준으로 깊이를 지정했다. 두 정점이 주어졌을 때 두 정점의 깊이를 맞추는 과정에서도 가중치의 합을 구해야 하는 것을 조심 해야한다. 두 정점의 깊이가 일치해 졌다면 같은 공통 조상까지 찾아가면서 가중치의 합을 구하면 최소 거리가 된다. 알고리즘 1. 간선과 가중치 정보를 입력 받는다. 2. 임의의.. Baekjoon 11437 LCA 2019. 4. 22. Link https://www.acmicpc.net/problem/11437 소스결과 7400 KB / 816 ms 언어 C++ 17 출처 Baekjoon 분류 LCA 설명 1을 루트로 하는 트리가 주어질 때 두 정점의 가장 가까운 공통 조상의 번호를 출력한다. LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다. 다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다. 예제를 직접 노트로 옮겨보니 바로바로 이어져서 입력과 동시에 깊이와 부모를 설정해 줬는데 제출을 하니 바로 시간초과에 걸렸었다. TC로 들어오는건 꼭 1이 있는 트리에 이어져서 들어오는게 아니라 나눠져 들어오기 때문에 깊이와 부모 설정에 문제가 생겨 높이를 맞추는 과정에서 무한루프에 빠지게 됬었.. 이전 1 다음 1/1
