🚩 코딩테스트/알고리즘
[백준] 1967번: 트리의 지름
딩딩크롱
2023. 5. 15. 23:30
728x90
문제
https://www.acmicpc.net/problem/1967
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연
www.acmicpc.net
풀이
DFS(깊이 우선 탐색)를 사용해 풀었습니다.
양방향 간선이므로 graph의 부모, 자식 노드에 해당하는 공간에 서로를 가중치와 함께 추가합니다.
트리의 지름을 구하는 방법은 다음과 같습니다.
- 루트 노드로부터 거리가 가장 먼 노드를 구합니다.
- 구한 노드로부터 거리가 가장 먼 노드까지의 거리를 구합니다.
코드
파이썬
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
n1, n2, w = map(int, input().split())
graph[n1].append((n2, w))
graph[n2].append((n1, w))
def DFS(x, w):
for nx, nw in graph[x]:
if distance[nx] == -1:
distance[nx] = w + nw
DFS(nx, distance[nx])
distance = [-1] * (n + 1)
distance[1] = 0
DFS(1, 0)
start = distance.index(max(distance))
distance = [-1] * (n + 1)
distance[start] = 0
DFS(start, 0)
print(max(distance))728x90