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

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

1167번: 트리의 지름

일단 이 문제는 입력도 은근 까다롭기 때문에 ㅋㅋ 입력부터 잘 받아보자.

무방향이지만 아래 코드처럼 입력받을 필요는 없다! 어차피 입력값에서 다 주어지기 때문이다.

tree[a].append((b,c))
tree[b].append((a,c))

그리고 이 문제는 '트리의 지름' 이란 키워드에 대한 이해가 필요하다. 단순히 임의의 한 노드에서 가장 멀리 있는 노드를 구하는 것이 아니라, 임의의 한 노드에서 가장 멀리 있는 노드가 지름을 구성하는 2개의 점 중 첫번째가 되는 것이고, 앞서 구한 노드에서부터 가장 멀리 있는 노드가 지름을 구성하는 2개의 점 중 2번째가 되는 것이다.

 

dist라는 배열을 하나 만들고, 이 배열에는 각 노드마다 해당 노드가 가질 수 있는 거리를 저장해준다. 다른 dfs와 마찬가지로 방문처리를 해주어야 하는데, dist 배열이 이 역할도 같이 하게 해주었다. 이렇게 되면 한가지 문제가 생기는데, 바로 부모에 대한 방문처리가 애매하다는 점이다. 파라미터로 노드의 부모 정보를 넘겨줘서 다시 부모로 들어가는 일이 없도록 해주었다.

 

point1 = max(range(1,v+1), key = lambda i : dist[i]) # 지름이 될 수 있는 한 점의 인덱스
# ==
point1 = dist.index(max(dist))

위 코드들은 dist 배열에서 가장 큰 값의 인덱스를 찾기 위한 코드이다. 이 문제에서 인덱스라 함은 트리 노드의 번호를 의미한다.

첫번째 코드에 대해서만 설명하자면 1부터 v까지의 값들이 순서대로 lambda i로 들어가고, 변수 i는 결국 dist 배열에서 제일 큰 값을 가리키는 인덱스를 의미하게 된다.

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

def dfs(now,parent):
  for next, weight in tree[now]:
    if dist[next]==0 and next != parent:
      dist[next] = dist[now]+weight
      dfs(next,now)

if __name__ == "__main__":
  v = int(input())
  tree = [[] for _ in range(v+1)]
  dist = [0 for _ in range(v+1)]
  
  for _ in range(v):
    arr = input()
    info = list(map(int, arr.split()[:-1]))
    node = info[0]
    for i in range(1,len(info),2):
      tree[node].append([info[i],info[i+1]])
  
  dfs(1,0) 
  point1 = max(range(1,v+1), key = lambda i : dist[i]) # 지름이 될 수 있는 한 점
  
  dist = [0 for _ in range(v+1)]
  
  point2 = dfs(point1,0) # 지름을 완성하는 두번째 점
  #print(dist)
  print(max(dist))