[백준/BOJ] gold2 - 1167번 트리의 지름 (Python)

▶1167 - 트리의 지름

백준 로고

▶문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

▶입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000) 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

▶출력

첫째 줄에 트리의 지름을 출력한다.

728x90

▶풀이

1967번 문제 트리의 지름과 똑같은 문제이다.

2023.04.10 - [BOJ Code/Gold] - [백준/BOJ] gold4 - 1967번 트리의 지름 (Python)

[백준/BOJ] gold4 - 1967번 트리의 지름 (Python)

차이점은 트리 노드 연결 관계를 입력하는 방식이 다르다.

1967번은 연결된 두 노드를 입력하고, 이번 문제는 각 노드에 연결된 노드를 모두 나열하는 방식이다.

그 부분만 수정해서 제출하니 정답이 나왔다.

 

그냥 for문을 통해서 해도 되고, 나는 deque를 이용해서 풀었다.

popleft를 이용해 좌측에서 하나씩 빼주면서 풀었더니 정답이 나왔다.

from collections import deque
import sys
sys.setrecursionlimit(10**6)


def dfs(x, weight):
    for a, b in graph[x]:
        if dist[a] == -1:
            dist[a] = b + weight
            dfs(a, weight + b)


n = int(input())
graph = [[] for _ in range(n + 1)]

for i in range(n):
    arr = deque(list(map(int, input().split())))
    a = arr.popleft()

    while True:
        b = arr.popleft()
        w = arr.popleft()

        graph[a].append([b, w])
        graph[b].append([a, w])

        if len(arr) == 1:
            break

dist = [-1 for _ in range(n + 1)]
dist[1] = 0
dfs(1, 0)

tmp = dist.index(max(dist))
dist = [-1 for _ in range(n + 1)]
dist[tmp] = 0
dfs(tmp, 0)

print(max(dist))