[🥇3 / 백준 1167 / 파이썬] 트리의 지름

 

1167번: 트리의 지름

 

문제

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

입력

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

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

출력

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

 

예제 입력  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

예제 출력  11

 

풀이

 

[🥇4 / 백준 1967 / 파이썬] 트리의 지름

 

위 문제와 아주 유사한 문제이다.

기본적인 풀이법은 같지만, 이번 문제에서는 뿌리 노드가 정해져있지 않다.

따라서 위 문제의 풀이와 달리 무방향 그래프라 가정하고 각 정점의 간선 정보를 받아 입력해야 한다.

그리고 임의로 뿌리 노드를 정한 뒤 visit 방문 배열에 방문 정점을 기록하며 지름을 찾아야 한다.

 

임의로 정한 뿌리 노드에 대해서는 꼭 방문 처리를 해줘야 한다.

 

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

n = int(input())
tree = [[] for _ in range(n+1)]
visit = [0]*(n+1)
maxDist = 0
for _ in range(n):
    tmp = list(map(int,input().split()))
    a = tmp[0]
    for i in range(1,len(tmp)-1,2):
        b,c = tmp[i],tmp[i+1]
        tree[a].append((b,c))

def dfs(n,d):
    left,right = 0,0
    for toNode, w in tree[n]:
        r = 0
        if not visit[toNode]:
            visit[toNode] = 1
            r = dfs(toNode,w)
        if left <= right:
            left = max(left,r)
        else:
            right = max(right,r)
            
    global maxDist
    maxDist = max(maxDist,left+right)
    return max(left+d,right+d)


visit[1]=1
dfs(1,0)
print(maxDist)