개발자꿀꿀이

문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 conpulake.tistory.com/62 백준 1761 (정점들의 거리) - LCA 풀이 문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 선형 시간의 LCA 알고리즘을 사용하였다. 해 conpulake.tistory.com 앞서 선형방식으로 간단하게 풀었지만 SparseTable을 이용해서 풀면 시간복잡도가 훨씬 줄어든다. conpulake.tistory.com/61 백준 11438 ( LCA 2) ..

문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 선형 시간의 LCA 알고리즘을 사용하였다. 해당 LCA까지의 간선 비용을 모두 합한 것이 두 정점 사이의 거리가 된다. 배열은 세개를 선언하였다 parents[] : 해당 정점의 바로 위 조상을 저장 하는 배열 parent_len[] : 해당 정점의 바로 위 조상과의 거리를 저장하는 배열 depth[] : 1번 정점을 제일 큰 조상을 두고 그로 부터의 깊이를 저장하는 배열 거리를 구하는 코드는 아래와 같다. public static int find_Dist(int a, int b) { if(depth[a] < depth[b]) {..