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

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

---

알고리즘 분류

• BFS

문제풀이

기본 알고리즘은 다음과 같다.
루트노드1번부터 모든 경로 중에서 최대값을 가지고 있는 노드 번호를 구한다.
그리고 그 번호로부터 다시 최대값을 구하면 된다.

tree딕셔너리를 나타내면 다음과 같다.
{1: [(2, 3), (3, 2)], 2: [(1, 3), (4, 5)], 3: [(1, 2), (5, 11), (6, 9)], 4: [(2, 5), (7, 1), (8, 7)], 5: [(3, 11), (9, 15), (10, 4)], 6: [(3, 9), (11, 6), (12, 10)], 7: [(4, 1)], 8: [(4, 7)], 9: [(5, 15)], 10: [(5, 4)], 11: [(6, 6)], 12: [(6, 10)]}

visited리스트를 통해 방문했으면 1로 바꾸어준다.
그리고 1번노드부터 BFS로 퍼지면서 각각의 노드까지 중간중간의 가중치를 계속 더해나가, 가중치가 최대값일 경우 그 값과 해당 노드 번호를 저장한다.

그리고 그 노드 번호부터 다시 bfs함수를 반복한다.
이번에는 그 값을 출력해주면 정답이다.

(처음에 딕셔너리에 존재하지 않는 키를 조회할 경우 발생하는 KeyError가 발생해서 뭔가 했더니 bfs(0)일 경우때문이더라... 그래서 tree딕셔너리를 0번부터 만들어주니 해결되었다..)

소스코드

from collections import deque

n=int(input())
tree={i:[] for i in range(n+1)}
for i in range(n-1):
  a,b,weight=map(int, input().split())
  tree[a].append((b,weight))
  tree[b].append((a,weight))

def bfs(s):
  queue=deque()
  queue.append((s,0))
  visited=[0]*n
  visited[s-1]=1

  result=[0,0]
  while queue:
    now,cnt=queue.popleft()
    for i in tree[now]:
      next_number,value=i[0],i[1]
      if visited[next_number-1]==0:
        visited[next_number-1]=1
        queue.append((next_number,cnt+value))
        if result[1]<cnt+value:
          result[0]=next_number
          result[1]=cnt+value

  return result

a=bfs(1)
b=bfs(a[0])
print(b[1])