Dijkstra3 [프로그래머스] 배달 / 파이썬 / Python / Dijkstra 💡solutions ) 💬 다익스트라 알고리즘을 사용하여 최단 거리를 구하는 로직 💬 처음 시작하는 노드 1에서의 최단 거리는 0으로 초기화 💬 인접행렬 만들고 -> heappush를 통해 최단 거리 순으로 정렬 -> 최단 거리가 될 때마다 거리를 저장해 놓는 리스트인 dis 업데이트 👨💻code ) import heapq def dijkstra(dis, adj): heap = [] heapq.heappush(heap, [0, 1]) while heap: cost, node = heapq.heappop(heap) for c, n in adj[node]: if cost + c < dis[n]: dis[n] = cost + c heapq.heappush(heap, [cost + c, n]) def solu.. 2021. 6. 14. [백준] 알고스팟 / 1261번 / 파이썬 / Python / Dijkstra 알고리즘 💡solutions ) 💬 단순 다익스트라(Dijkstra) 알고리즘으로 해결한 문제, 해당 문제에서 노드의 비용에 해당하는 것은 벽을 부순 횟수(cnt) 💬 BFS로도 방문 중복으로 하여 해결할 수 있는 문제 🎫code ) import sys import heapq def dijkstra(): heap = [] heapq.heappush(heap, [0, 0, 0]) # 시작점 visit[0][0] = 1 while heap: cnt, x, y = heapq.heappop(heap) # 벽 부순 횟수가 최소인 경우가 나옴 for k in range(4): nx, ny = x + dx[k], y + dy[k] if x == n - 1 and y == m - 1: # 종료조건 print(cnt) break.. 2020. 12. 6. [백준] 최단경로 / 1753번 / 파이썬 / Python / Dijkstra 💡solutions ) 💬 이번 문제는 최단 경로를 풀 때 가장 대표적인 다익스트라 알고리즘을 통해 해결했다. 💬 heap 자료구조 사용하여 heappop()을 했을 때 가장 최단 경로가 나오게 한다. 🎫code ) import heapq import sys input = sys.stdin.readline def dijkstra(v, s, adj): dist = [INF] * (v + 1) # 최단경로 리스트 dist[s] = 0 heap = [] heapq.heappush(heap, [0, s]) while heap: cost, node = heapq.heappop(heap) # 최소힙 이용 for n, c in adj[node]: c += cost if c < dist[n]: dist[n] = c h.. 2020. 10. 9. 이전 1 다음
