본문 바로가기
728x90

다익스트라6

[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.
[PG/Python] 배달 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 📌 문제 접근 방법 다익스트라 알고리즘을 사용하였다. 우선 각각의 노드간의 연결 관계를 인접행렬에 저장해주었다. 연결 관계가 2개 이상인 경우도 있기에, 이미 값이 있다면 최소의 거리를 저장하도록 했다. distance라는 리스트를 만들어서 여기에 해당 노드까지 가는 최소 거리를 저장하였다. 항상 출발지는 1번 노드이므로 1번 .. 2021. 12. 16.
[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.
728x90

티스토리툴바