문제링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제풀이 - 인접 리스트 사용해서 DFS 탐색 2번 수행 - 시간 복잡도 : O(V + E) 절차 1) 1번 루트 노드에서 가장 비용이 큰 리프(leaf)노드를 찾음 (= 지름에 해당하는 한점) 2) 찾은 리프 노드를 시작점으로 dfs 탐색을 한번 더 수행하여 구한 최대 cost가 트리의 지름이다 참고. 동일 문제 https://dev-ljw1126.tistory.co..

문제 링크 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 풀이 - 앞서 MST 문제 풀이하다가 '트리의 지름'에 대한 이론을 알게 되었고, 관련 문제 풀이함 '트리의 지름'에 대한 강의 영상을 찾아보니 초보 알고리즘이란다 (하하하.. 심플하긴하다) https://dev-ljw1126.tistory.com/369 [BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름) 문제 링크 http..

문제 링크 https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 문제 풀이 최소 가중치를 가지는 MST는 구했는데, 두번째 값을 구하지 못해 3시간을 소비했다. 찾아본 결과 트리의 지름을 구하는 방법을 몰랐고, 문제 지문을 제대로 읽지 못해 MST 트리 정보를 활용하는 것을 파악하지 못했다..(반성) 문제 지문을 다시 보면 아래와 같다 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 (1)모든 마을과 마을을 ..