Algorithms/Shortest Path
-
[다익스트라 알고리즘] 미로만들기Algorithms/Shortest Path 2021. 8. 29. 16:55
기출: 백준 #2665 from heapq import heappush, heappop INF = int(1e9) dx = [1,-1,0,0] dy = [0,0,1,-1] n = int(input()) distance = [[INF for _ in range(n)] for __ in range(n)] distance[0][0] = 0 visited = [[False for _ in range(n)] for __ in range(n)] graph = list() for _ in range(n): graph.append(input()) queue = list() heappush(queue, (0,(0,0))) while queue: curVal, cur = heappop(queue) if distance[c..
-
[플로이드 워셜 알고리즘] 맥주 마시면서 걸어가기Algorithms/Shortest Path 2021. 8. 29. 14:49
기출 : 백준 #9205 from collections import deque INF = int(1e9) t = int(input()) def calcDist(st, en): dist = abs(st[0]-en[0]) + abs(st[1]-en[1]) if dist>1000: return INF return dist for _ in range(t): n = int(input()) node = [] graph = [[INF for _ in range(n+2)] for __ in range(n+2)] home = list(map(int,input().split())) node.append(home) for i in range(n): node.append(list(map(int,input().split()))..
-
[다익스트라 알고리즘] 케빈 베이컨의 6단계 법칙Algorithms/Shortest Path 2021. 8. 29. 11:11
기출 : 백준 #1389 INF = int(1e9) n, m = map(int,input().split()) graph = [[] for _ in range(n+1)] distance = [INF for _ in range(n+1)] answerArr = [0 for _ in range(n+1)] answerVal = INF answer = 0 for _ in range(m): a, b = map(int,input().split()) graph[a].append([1, b]) graph[b].append([1, a]) def dijkstra(start): distance[start] = 0 queue = [[0,start]] while queue: curVal, cur = queue.pop(0) if d..
-
[다익스트라 알고리즘] 알고스팟Algorithms/Shortest Path 2021. 8. 15. 12:19
기출 : 백준 #1261 from heapq import heappush, heappop INF = int(1e9) dx, dy = [1,-1,0,0], [0,0,1,-1] m, n = map(int,input().split()) board = list() for _ in range(n): board.append(list(input())) distance = [[INF for __ in range(m)] for _ in range(n)] distance[0][0] = 0 queue = list() heappush(queue, (0,[0,0])) while queue: curVal, cur = heappop(queue) curX, curY = cur # 이미 계산한 경우 if distance[curX][c..
-
[다익스트라 알고리즘] 특정한 최단 경로Algorithms/Shortest Path 2021. 8. 13. 16:29
기출 : 백준 #1504 1 -> v1 -> v2 -> n 1 -> v2 -> v1 -> n 위의 두 가지 경로를 고려하여 최솟값을 출력하면 된다 from heapq import heappop, heappush INF = int(1e9) n, e = map(int,input().split()) graph = [[]for _ in range(n+1)] queue = list() for _ in range(e): x,y,w = map(int,input().split()) graph[x].append((w, y)) graph[y].append((w, x)) v1, v2 = map(int,input().split()) def dijkstra(start, end): distance = [INF for _ in r..
-
[다익스트라 알고리즘] 최소비용 구하기Algorithms/Shortest Path 2021. 8. 13. 16:07
기출 : 백준 #1916 일반적인 다익스트라 문제이다 from heapq import heappush, heappop INF = int(1e9) n = int(input()) m = int(input()) distance = [INF for _ in range(n+1)] graph = [[] for _ in range(n+1)] for _ in range(m): x, y, w = map(int,input().split()) graph[x].append([w,y]) start, end = map(int,input().split()) def djikstra(start): queue = list() distance[start] = 0 heappush(queue, (0,start)) while queue: cu..
-
[다익스트라 알고리즘] 최단경로Algorithms/Shortest Path 2021. 8. 13. 15:35
기출 : 백준 1753 일반적인 다익스트라 문제다 두 정점 사이에 여러 간선이 있을 수 있다는 점을 고려해야 한다 from heapq import heappush, heappop INF = int(1e9) v, e = map(int, input().split()) k = int(input()) distance = [INF for _ in range(v+1)] minVal = dict() graph = [[] for _ in range(v+1)] queue = list() for _ in range(e): x, y, w = map(int,input().split()) if x not in minVal: minVal[x] = dict() if y not in minVal[x]: minVal[x][y] = w..
-
[최단 경로 알고리즘] 문제풀이 전략 #2 플로이드 워셜 알고리즘Algorithms/Shortest Path 2021. 2. 17. 16:31
다익스트라 알고리즘은 한 노드에서 다른 모든 노드로 향하는 최단 경로를 구하는 것이 목적이다 하지만 이번에 알아볼 플로이드 워셜 알고리즘은 모든 노드에서 모든 노드로 향하는 최단 경로를 구하는 알고리즘이다 알고리즘의 핵심은 노드 N에 대해서 N을 제외한 모든 노드가 N을 거쳐 다른 노드로 이동하는 거리를 갱신하는 것이다 이를 점화식으로 표현하면 Dab = min(Dab,Dak+Dkb)이다 N개의 노드에 대해서 각 단계를 수행하고 각 단계는 (N-1)P2 이므로 시간 복잡도는 O(N^3)이 된다 이를 바탕으로 소스 코드를 작성하면 다음과 같다 #include #define inf 1e9 using namespace std; int n, m; int a, b, c; int graph[100][100]; in..