[백준 1167] 트리의 지름 - python (solved.ac - 골드 3)

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

1167번: 트리의 지름

풀이

문제를 보았을때 알수있는 힌트

문제를 처음 풀었을때 dfs, bfs로 접근하면 되겠구나 라는 생각은 들었다. 접근은 잘했지만 정점 1부터 n까지 반복하여 돌리면 시간 초과가 나온다. 이것을 통해 뭔가 다른 조건이 하나 더 있겠구나! 라는 생각이 들었다. 

이 조건을 찾기 위해서는 https://blog.myungwoo.kr/112 이 블로그를 참고했다.

블로그에서는 임이의 정점 한곳을 잡고 거기서 가장 먼 정점을 찾게 된다면 찾게된 정점에서 다시 가장 먼 정점을 찾았을때 그때가 최대의 길이가 된다는 것이다.

다시 말해 정점을 1부터 n까지 돌릴 필요없이 딱 2번만 돌리면 결과가 나온다는 것을 알았다.

다음에 트리의 지름이나 최대의 길이를 푸는 문제가 있다면 이렇게 문제를 해결하는 것이 좋을듯하다.

 

import sys
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def dfs(x,count):
    global total_count
    global totla_temp
    if total_count<count:
        total_count=count
        totla_temp = x
    if visited[x]==False:
        visited[x]=True
        for i in graph[x]:
            if visited[i[0]]==False:
                count+=i[1]
                dfs(i[0],count)
                count-=i[1]

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n):
    temp = list(map(int,input().split()))
    for i in range(1,len(temp)-2,2):
        graph[temp[0]].append([temp[i],temp[i+1]])
total_count=0
totla_temp=1
visited =[False for _ in range(n+1)]
dfs(1,0)

visited =[False for _ in range(n+1)]
total_count=0
dfs(totla_temp,0)

print(total_count)

 

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1167.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리