[프로그래머스] 그래프 - 가장 먼 노드 (결과 포함)
문제 자체에 그래프, 노드, 최단 경로라는 단어들이 등장하기 때문에 최단경로 알고리즘을 사용해야겠다고 생각했다. 특정 시작 지점으로부터 가장 멀리있는 노드들의 개수를 구하는 것이 문제이다. 다익스트라 최단경로 알고리즘을 이용하여 시작 노드에서 다른 노드로 이동할 때 최단경로의 길이를 저장했다. distance 리스트에 각 노드로 이동할 때 최단경로의 길이를 저장한다. 최초에는 굉장히 큰 수 (1e9)를 저장해놓고 인덱스에 해당하는 노드까지의 거리가 더 작으면 대체하는 식이다. 다익스트라 알고리즘이 끝난 후에 distance 리스트를 필터링한 이유는 가장 먼 노드의 거리를 구할 때, 최초에 비교를 위해 넣은 큰 수(1e9)가 나오지 않게 하기 위해서이다. 간과했던 부분은 간선이 양방향이라는 사실이었다. 간..
개발 공부 (알고리즘)
2021. 8. 23. 03:19
