[백준] 1167번 트리의 지름 [Python]

 

 

트리의 지름을 구하는 문제

N개의 노드에 대해서

각 노드마다 한 줄에 그 노드, 연결된 노드1, 거리1, 노드2, 거리2, ... -1 이런 구조로 정보가 주어진다.

예$)$ 3, 1, 2, 4, 3, -1 >>> 3과 1은 거리가 2; 3과 4는 거리가 3; -1: 끝 의미

 

트리$($tree$)$는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

트리의 지름

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

 

문제

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

입력

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

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

출력

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

https://www.acmicpc.net/problem/1167

 

문제: https://www.acmicpc.net/problem/1967

문제 풀이 https://savvy0402.tistory.com/236

 

위 문제 풀이와 같은 방식으로 함수를 구현해서 풀이함.

 

아무 번호$($여기서는 1번$)$에서 출발해서 가장 먼 노드를 구한 뒤,

그 노드에서 또 가장 먼 노드까지의 거리를 구해서 출력함. $($위 문제 풀이 글에 이 방법에 대한 설명을 좀 적어뒀음$)$

 

import sys
input = sys.stdin.readline

def main():
    V = int(input())
    graph = [[] for _ in range(V+1)]
    for _ in range(V):
        a, *li = map(int, input().split())
        for b, c in zip(li[::2], li[1::2]):
            graph[a].append((b, c))

    def dfs(s, V, flag=False):
        dist = 0
        v = [False]*(V+1)
        stack = [(s, 0)]
        while stack:
            n0, d0 = stack.pop()
            if dist < d0:
                s, dist = n0, d0
            v[n0] = True
            for n1, d1 in graph[n0]:
                if not v[n1]:
                    stack.append((n1, d0 + d1))
        if flag:
            return dist
        return s

    print(dfs(dfs(1, V), V, True))

if __name__ == "__main__":
    main()

 

 

 

예제 입력 1 

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

예제 출력 1 

11