프로그래머스 [가장 먼 노드]

문제

2021.12.30

문제 보기

다음과 같은 그래프가 주어졌을 때 1번 노드에서 최단거리로 갔을 때 가장

멀리 떨어진 노드를 구하는 문제이다.

본인은 dijkstra 알고리즘을 써서 각 노드 까지의 거리를 구하여 풀었다.

얻어간 지식

모든 노드 사이의 거리가 일정하므로 bfs를 써도 풀 수 있다.

dijkstra와 bfs의 차이는 'weighted cost를 고려할 수 있는지' 이다.

---

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

edge가 위와같이 [node, node] 형태로 주어졌을 때

이 상태로 탐색을 하게 되면 다음 노드로 진행 할 때 마다 배열을 모조리 탐색해야 한다.

[0, [3, 2], [3, 1, 4, 5], [6, 4, 2, 1], [3, 2], [2], [3]]

다음과 같이 정리하면 다음 노드로 진행할 때 탐색에 걸리는 시간을 줄일 수 있다.