목록백준 1753 (1)

시작이 반

[백준] 1753번번 (python 파이썬)

다익스트라 알고리즘이다. 다익스트라 알고리즘은 edge의 가중치가 양수만 있을때 사용할 수 있다. 2가지 방법으로 풀 수 있다. 1. 해당 노드에서 이어진 노드들중 가중치가 가장 작은 경로를 선택한다. 2. 우선순위 큐를 사용하여 해결할 수 있다. 우선순위 큐를 이용하여 풀었다. (가장 작은 가중치를 선택해야함) 파이썬에서는 우선순위 큐를 사용하기위해 heapq를 사용할 수 있다. (동작은 min heap인듯 하다) 다익스트라를 풀기위해 필요한 것들 1. 우선순위 큐에 사용될 list ( queue = list() ) 2. 가중치를 저장할 list ( distance = list() ) 세팅 distance[시작점] = 0 우선순위 큐에 (해당 점의 가중치, 해당점) 을 넣는다. queue가 빌때까지 반..
알고리즘/백준 2021. 3. 20. 01:40
이전 Prev 1 Next 다음