데이크스트라 검색 결과
1 개의 검색 결과가 있습니다.
알고리즘 문제풀이[Algorithm]

[백준] 1753번 최단경로(다익스트라 알고리즘)(Python - 파이썬)

백준 1753번 문제입니다. (solved.ac)기준 골드 5 문제입니다. 문제 접근 시작점이 주어졌기 때문에 다익스트라 알고리즘을 이용하여 간단하게 최단 경로를 구할 수 있는 문제입니다. 그래프의 노드를 가리키는 정점(V)의 개수의 범위가 20,000 이하이기 때문에 시간복잡도가 O(V^2)인 간단한 다익스트라 알고리즘으로는 시간초과 오류가 발생할 것입니다(V는 노드의 개수). 따라서 우선순위 큐를 사용하여 개선된 다익스트라 알고리즘으로 문제를 해결하였습니다. 개선된 다익스트라 알고리즘은 최악의 경우에도 시간 복잡도가 O(ElogV)로 보장됩니다(V는 노드의 개수, E는 간선의 개수). 개선된 다익스트라 알고리즘은 1. 출발 노드(start)를 설정 2. 최단 거리 테이블(distance)을 int(1..

2022. 2. 22. 03:23