[백준1167&파이썬] 트리의 지름을 BFS를 사용해 구하자. 트리는 사이클이 존재하지 않는다.

# 문제

백준 1167 트리의 지름 파이썬 풀이

1167번: 트리의 지름

# 코드

import sys
from collections import defaultdict
from collections import deque

# 정점의 개수
V = int(sys.stdin.readline().strip())
trees = defaultdict(list)

for _ in range(V) :
  line = list(map(int,sys.stdin.readline().split()))

  node = line[0]
  loop_idx = 1
  while loop_idx < len(line)-1 :
    trees[node].append((line[loop_idx], line[loop_idx+1]))
    loop_idx+=2

# 현재 트리는 양방향 연결인 점에 주의
# 무작위 한 정점에서 가장 거리가 먼 곳을 찾는다.
  # 이번엔 BFS를 이용해서 찾아보자.
  # 트리는 애초에 사이클이 없다.

# 시작노드로부터 멀리 떨어진 노드를 찾는다.
def bfs(start) :
  global trees, V

  dq = deque()
  visit = [-1] * (V+1)
  visit[start] = 0
  dq.append((start,0))

  while len(dq) != 0 :
    cur_node, cur_weight = dq.popleft()
    for next_node, next_wieght in trees[cur_node] :
      if visit[next_node] == -1 :
        visit[next_node] = cur_weight + next_wieght
        dq.append((next_node,visit[next_node]))

  return visit

distance = bfs(1)
print(max(bfs(distance.index(max(distance)))))

# 풀이

• 똑같은 문제가 백준 1967에 있고 어제 해당 문제를 풀었다.
• 두 문제의 차이점은 입력 방시에 대한 차이이다.
• 입력을 파이썬을 푸는 사람 입장에서는 다소 불친절하게 주기 때문에 입력을 잘 받아주자.
• 예제의 입력에 대한 트리를 구성하면 아래와 같다.

• 트리의 지름을 구하기 위해서는 한 정점에서 시작하여 가장 먼 곧을 찾는다. 그리고 그 곧은 리프노드가 되며 지름을 이루는 한 끝점이 된다.
• 이어서 해당 끝점에서 가장 먼 정점을 찾고 그 정점까지의 거리가 트리의 지름이 된다.
• 트리는 사이클이 존재하지 않는다는 점에서 BFS로 쉽게 구현이 가능했다. 저번에는 다익스트라로 풀었는데 BFS가 더 좋은 풀이인거 같다.