프로그래머스: 가장 먼 노드 - 시바견의 끄적임

프로그래머스: 가장 먼 노드 - 시바견의 끄적임

728x90

다익스트라 알고리즘을 사용한다.

참고: https://focalpoint.tistory.com/6

import heapq def solution(n, edge): answer = 0 max_dist = 0 graph = [[] * (n+1) for _ in range(n+1)] for e in edge: u, v = e graph[u].append(v) graph[v].append(u) distance = [int(1e9)] * (n+1) pq = [] heapq.heappush(pq, (0, 1)) distance[1] = 0 while pq: dist_u, u = heapq.heappop(pq) if dist_u > max_dist: answer = 1 max_dist = dist_u elif dist_u == max_dist: answer += 1 if distance[u] < dist_u: continue for v in graph[u]: if distance[v] > dist_u + 1: distance[v] = dist_u + 1 heapq.heappush(pq, (distance[v], v)) return answer

from http://focalpoint.tistory.com/164 by ccl(A) rewrite - 2021-11-05 21:26:37