코드 import sys, heapq input = sys.stdin.readline INF = 987654321 n,m = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [INF]*(n+1) for _ in range(m): a,b,c = map(int, input().split()) graph[a].append((b,c)) graph[b].append((a,c)) def dijkstra(): queue = [(0,1)] visited[1] = 0 while queue: cost, vertex = heapq.heappop(queue) if cost > visited[vertex]: continue for ver in graph..
다익스트라 알고리즘
코드 # bfs로 해결할 수 있을 거라 생각했지만, 가중치가 달라서 다익스트라 알고리즘 이용 import sys, heapq input = sys.stdin.readline INF = 987654321 tc = int(input()) def dijkstra(node, zido, hi): queue = [(0,node)] hi[node] = 0 while queue: now, next = heapq.heappop(queue) if now > hi[next]: continue for i in zido[next]: dist = now + i[1] if hi[i[0]] > dist: hi[i[0]] = dist heapq.heappush(queue, (dist, i[0])) for _ in range(tc): ..
코드 import sys, heapq input = sys.stdin.readline INF = 987654321 n,m = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [INF]*(n+1) # 양방향 그래프를 만들어 준다. for _ in range(m): a,b,c = map(int, input().split()) graph[a].append((b,c)) graph[b].append((a,c)) def dijkstra(start): queue = [(0, start)] visited[start] = 0 while queue: now, next = heapq.heappop(queue) if now > visited[next]..
코드 # 처음 시작, 마지막 점 도착 => 한 점에서 다른 한 점으로의 최단거리 # 가중치는 0~9사이의 정수이므로 다익스트라 알고리즘 사용 가능 # 상하좌우 움직이는 경우를 파악해야 하므로 bfs 풀이 아이디어를 빌려온다. from heapq import heappop, heappush import sys INF = 987654321 input = sys.stdin.readline def dijkstra(first,x,y): dx,dy = [1,-1,0,0], [0,0,1,-1] # 상하좌우 움직일 경우의 수 queue = [(first, x,y)] # 비용, 행, 열 visited[x][y] = first while queue: now, popx,popy = heappop(queue) if now >..
코드 1 (BFS 이용) import sys from collections import deque input = sys.stdin.readline n,m,k,x = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [0]*(n+1) # 방문 기록용 for _ in range(m): s,e = map(int,input().split()) graph[s].append(e) # 단방향 그래프 def bfs(start): queue = deque([start]) visited[start] = 1 while queue: num = queue.popleft() for i in graph[num]: if not visited[i]: visite..
코드 # start, x -> x, start 최단거리 기록 # 오고 갈 수 있는 데이터만 입력으로 주어짐 import heapq, sys # 우선순위 큐를 이용한 다익스트라 구현을 위해 heapq import input = sys.stdin.readline # 빠른 입력 INF = 987654321 # 무한대 n,m,x = map(int, input().split()) # 노드의 수, 간선의 수, 도착지점 graph = [[] for _ in range(n+1)] for _ in range(m): start, end, dist = map(int,input().split()) graph[start].append((end, dist)) # 단방향 그래프 def dijkstra(start, end): # 다..
코드 import sys, heapq # 우선순위 큐를 이용한 다익스트라를 구현할 용도 input = sys.stdin.readline INF = 987654321 # 무한대 n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a,b,c = map(int,input().split()) graph[a].append((b,c)) # 양방향 길 graph[b].append((a,c)) v1,v2 = map(int,input().split()) # 꼭 들러야 할 길 def dijkstra(start,end): # 다익스트라 알고리즘 queue = [(0,start)] visited = [INF] * (n+1) # v..
다익스트라 알고리즘 다익스트라 알고리즘은 가중치가 양수만 존재하는 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘 중의 하나이다. 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복한다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다고 한다. 참고로, 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등이 있다. 동작 단계 1. 출발 노드와 도착 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 현재 위치한 도드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드..
