[python]백준 1167 풀이

트리의 지름

백준 1167 문제 링크

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

입력

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

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

출력

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

풀이

백준 1967 문제 풀이 링크
이 문제는 백준 1967 문제와 굉장히 동일한 문제입니다. 마찬가지로 임의의 노드에서 가장 큰 가중치를 갖는 노드는 트리의 지름 중 한 노드라는 성질을 이용해서 두번의 DFS를 사용하여 해결할 수 있습니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

# DFS를 이용해서 가중치를 기록
def dfs(node, weight):
    for c, w in graph[node]:
        total = weight + w
        if visited[c] == -1:
            visited[c] = total
            dfs(c, total)

# 정점의 수
v = int(input())
# 그래프 연결 정보를 저장하는 배열
graph = [[] for _ in range(v+1)]
# 각 그래프의 연결정보를 입력받아 저장
for _ in range(v):
    arr = list(map(int, input().split()))
    node = arr[0]
    # 각 연결정보는 1, 3, 5, ... 순으로 입력됨
    for j in range(1, len(arr)-1, 2):
        n, w = arr[j], arr[j+1]
        graph[node].append((n, w))
visited = [-1 for _ in range(v+1)]
visited[1] = 0
# 지름 중 한 정점을 찾기 위한 DFS
dfs(1, 0)
start, tmp = 0, 0
for i in range(1, v+1):
    if visited[i] > tmp:
        start, tmp = i, visited[i]
visited = [-1 for _ in range(v+1)]
visited[start] = 0
# 지름을 구하기 위한 DFS
dfs(start, 0)
print(max(visited))

가장 먼저 트리의 연결 정보를 담을 배열을 선언해줍니다. 그리고 각 정점의 연결정보는 문제에서의 설명처럼 들어오게 되는데, 가장 먼저 정보의 첫번째 수는 정점이니까 해당 정점에 (1, 2), (3, 4) 순으로 정보를 저장합니다. 어짜피 -1 정보는 필요가 없으므로 제외합니다.

이후에 두번의 DFS를 수행하여 트리의 지름을 구하면 문제를 해결할 수 있습니다.