본문 바로가기
반응형

데이크스트라10

[BOJ][Python]14938 풀이 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net import sys; ssr = sys.stdin.readline import heapq INF = 16 n, m, r = map(int, ssr().split()) items = list(map(int, ssr().split())) routes = [[] for _ in range(n+1)] ans = 0 for _ in range(r): a, b, l = map(int, ssr().split()) .. 2023. 10. 22.
[BOJ][Python]11779 풀이 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 1000000001 def dijkstra(start, end): min_costs = [INF for _ in range(n+1)] min_costs[start] = 0 min_route = [0 for _ in range(n+1)] min_route[start] =.. 2023. 10. 10.
[BOJ][Python]9370 풀이 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 2000001 def dijkstra(start, end=None): h = [(0, start)] min_dist = [INF for _ in range(n+1)] min_dist[start] = 0 while h: cur_dist, cur_node = heapq.heappop(h) if cu.. 2023. 8. 3.
[BOJ][Python]1238 풀이 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 1000001 def dijkstra(start, edges): time = [INF for _ in range(n+1)] time[start] = 0 h = [(0, start)] while h: cur_time, cur_node = heapq.heappop(h) if.. 2023. 8. 2.
[BOJ][Python]13549 풀이 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 100001 def dijkstra(n, k): # -1, 1, *2 h = [(0, n)] time = [INF for _ in range(200001)] time[n] = 0 while h: cur_time, cur_node = heapq.heappop(h) .. 2023. 8. 1.
[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드 저를 가장 오랫동안 괴롭혔던 알고리즘 중에 하나인 데이크스트라 알고리즘에 대해서 정리를 해볼까합니다. 그 때의 헤매던 저와 비슷한 분들께 도움이 되면 좋겠네요. 데이크스트라(Dijkstra) 최단 경로 알고리즘 최단 경로라는 말에서 짐작할 수 있듯이 데이크스트라 알고리즘은 출발점에서 도착점까지 가장 빠르게 갈 수 있는 경로를 탐색하는 알고리즘입니다. 최단 경로를 구하는 알고리즘에는 대표적으로 데이크스트라, 플로이드-워셜, 벨만-포드, A*(에이 스타) 이렇게 네가지가 있으며 이번 포스팅에서는 데이크스트라 알고리즘에 대해서만 정리를 해보겠습니다. 알고리즘의 이름인 데이크스트라는 알고리즘의 고안자인 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라(Edsger Dijkstra)의 이름을 따서 부르고 있습니다. 한.. 2023. 8. 1.
[BOJ][Python]1504 풀이 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 200000001 def dijkstra(start, end): h = [(0, start)] min_dist = [INF for _ in range(n+1)] min_dist[start] = 0 while h: cur_dist, cur_node = hea.. 2023. 8. 1.
[BOJ][Python]1753 풀이 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 3000001 def dijkstra(start): h = [(0, start)] dist[start] = 0 while h: cur_dist, cur_node = heapq.heappop(h) if cur_dist > dist[cur_node]: continue.. 2023. 8. 1.
[BOJ][Python]18352 풀이 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 300001 def dijkstra(): while h: cur_dist, cur_node = heapq.heappop(h) if cur_dist > dist[cur_node]: continue for next_dist, nex.. 2023. 7. 31.
[BOJ][Python]1916 풀이 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 100000000 def dijkstra(start, arrive): min_cost = [INF for _ in range(n+1)] h = [] heapq.heappush(h, (0, start)) # 거리, 도착 순서 min_cost[start] = 0 whil.. 2023. 7. 19.
반응형

티스토리툴바