[백준][Python] 1595 북쪽나라의 도로 : 함수 재활용 시 반환값에 주의

[백준][Python] 1595 북쪽나라의 도로 : 함수 재활용 시 반환값에 주의

트리의 지름 문제. bfs 두번을 통해 최대 거리를 두번 산출해주면 된다.

조금 중요한게 graph배열을 1부터가 아니라 0부터 만들어 주어야 한다는점.

(노드가 1개일때 내가 노드를 1로 설정해둬서.. 지금보니 그냥 target_node를 1로 설정해 주었다면 1부터 해도 될것같다)

import sys input = sys.stdin.readline from collections import deque def bfs(start): q = deque() q.append((start, 0)) visited = [False for __ in range(10001)] visited[start] = True max_dist = 0 target_node = 0 while q: cur_node, cur_dist = q.popleft() for next_node, next_dist in graph[cur_node]: if visited[next_node]: continue visited[next_node] = True dist = next_dist + cur_dist if dist > max_dist: max_dist, target_node = dist, next_node q.append((next_node, dist)) return (target_node, max_dist) edges = [] while 1: try: a, b, c = map(int, input().split()) edges.append((a, b, c)) except: break n = len(edges) graph = {i: [] for i in range(10001)} for edge in edges: a, b, c = edge graph[a].append((b, c)) graph[b].append((a, c)) print(bfs(bfs(1)[0])[1])

from http://devlibrary00108.tistory.com/589 by ccl(A) rewrite - 2021-10-07 17:01:31