파이썬 다익스트라 (2) 썸네일형 리스트형 백준 4485번: 녹색 옷 입은 애가 젤다지? 파이썬 코드(다익스트라) import sys import heapq INF = sys.maxsize x = [0,0,-1,1] y = [-1,1,0,0] count = 0 while 1: n = int(sys.stdin.readline()) count += 1 visited = [[0 for _ in range(n)]for _ in range(n)] if n == 0: break graph = [] dist = [[INF for _ in range(n)] for _ in range(n)] for i in range(n): temp = list(map(int, sys.stdin.readline().split())) graph.append(temp) heap = [] heapq.heappush(heap, [graph[0][0],[0.. 파이썬 다익스트라 알고리즘 사용하기 다익스트라 알고리즘 다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 '에츠허르 데이크스트라'라서 라고한다. 이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다. 다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다. 초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다. 과정 (그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용) 상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다. (보라색 정점 = 0, .. 이전 1 다음
