본문 바로가기
728x90

Dijkstra5

[PG/Python] 합승 택시 요금 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 📌 문제 접근 방법 다익스트라 알고리즘을 사용하여 풀이하였다. 가장 중점이.. 2022. 1. 14.
[Algorithm] 다익스트라(dijkstra) 알고리즘 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지 최단 경로 다익스트라 알고리즘 : 음의 가중치 허용x 벨만-포드 알고리즘 : 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드 워샬 알고리즘 다익스트라(dijkstra) 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해나가면서 최단 경로 구함 탐욕 기법 사용, MST의 프림 알고리즘과 유사 def dijkstra(start): distance[start] = 0 # 노드의 개수만큼 반복 for _ in range(N+1): min_idx = -1 min_value = float('inf') for i in range(N+1): if not visit.. 2021. 10. 21.
[SWEA/Python] 1795. 인수의 생일 파티 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 다익스트라 알고리즘 사용 처음에는 모든 인접한 노드의 시간을 갱신하고, 그 중 최소값을 찾아서 이동하였는데 시간초과 bfs를 사용해서 시간이 더 줄어드는 경로로만 이동하는 방식으로 구현했더니 통과하였다. 📌 코드 import sys sys.stdin = open('input.txt') def dijkstra(start, end): time[start] = 0 for _ in range(N): min_idx = -1 min_time = float('inf') for.. 2021. 10. 19.
[SWEA/Python] 1249. 보급로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 다익스트라 알고리즘 사용 출발지에서 인접한 위치를 탐색하며 원래 저장된 비용보다 현재 경로로 온 비용이 적다면 비용을 갱신하고, 현재 위치를 큐에 넣는다. 큐가 빌 때까지 2를 반복 후, 도착지에 저장된 비용을 출력한다. 📌 코드 from collections import deque import sys sys.stdin = open('input.txt') def restore(i, j): queue = deque() queue.append((i, j)) dxy =.. 2021. 10. 19.
728x90

티스토리툴바