1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

문제

문제를 설명하면 한 노드에서 다른 모든 노드들 중 최단 거리 값이 distanceThreshold보다 작거나 같은 것을 원하고 있다. 즉 Example1을 보자면 city0에서 city1, city2, city3까지 각 최단 거리는 (3, 4, 5)가 되는데 distanceThreshold가 4이므로 city3는 제외가 된다. 즉 city0 -> [city1, city2]가 되는 것이다. 즉 최단 거리 알고리즘을 사용하면 된다.

풀이(다익스트라 알고리즘)

다익스트라 알고리즘은 쉽게 말해 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단경로를 알려준다. dijkstra함수는 힙큐를 사용한 다익스트라 알고리즘이고 문제에서 원하는 것은 모든 노드를 계산해보아야 하기 때문에 출발 노드를 for문을 통해 해결하였다.

결과(다익스트라 알고리즘)

풀이(플로이드 워셜 알고리즘)

플로이드 워셜은 다익스트라와 다르게 모든 노드마다 최단 경로를 알려준다. 하지만 이 알고리즘은 시간복잡도측면에서 N^3이기 때문에 적합한 문제에 사용해야 한다. 이 문제에서는 모든 노드마다 최단 경로를 알아야 하므로 적합하다.

결과(플로이드 워셜 알고리즘)