해킹왕 양선규

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) board = [] for _ in range(N): # 미로 입력받기 board.append(list(map(int, input().strip()))) distroy = [[INF for _ in range(N)] for _ in range(N)] # 부순갯수 visited = [[False for _ in range(N)] for _ in range(N)] # 방문목록 def goingNogoing(x, y): # 갈지말지 정하는함수 if 0

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) # 도시 개수 ( 노드 개수 ) E = int(input()) # 버스 개수 ( 간선 개수 ) graph = [[] for _ in range(N + 1)] for _ in range(E): a, b, c = map(int, input().split()) # 출발노드, 도착노드, 거리 입력받기 graph[a].append([c, b]) # (거리, 도착노드) start, end = map(int, input().split()) # 계산해야 할 출발지, 도착지 distance = [INF] * (N + 1) # 최단 경로 리스트 def dijkstra(star..

import heapq import sys INF = int(1e9) input = sys.stdin.readline N, E, K, start = map(int, input().split()) # 노드, 간선, 찾을거리, 출발노드 graph = [[] for _ in range(N + 1)] for _ in range(E): a, b = map(int, input().split()) # 출발노드, 도착노드 graph[a].append([1, b]) # 거리(1), 도착노드 distance = [INF] * (N + 1) def dijkstra(start): queue = [] heapq.heappush(queue, (0, start)) # 시작노드거리, 시작노드 큐에 삽입 distance[start] ..

다익스트라(dijkstra) 알고리즘(최단 경로 알고리즘) - 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘 - 이 과정에서 도착 정점 뿐만 아니라, 모든 다른 정점까지 최단 경로로 방문한다. - 최단 경로를 구하는 과정에서, “각 노드에 대한 현재까지의 최단 거리” 정보를 항상 저장하고 갱신한다. - 매번 가장 비용이 적은 노드를 선택하는 것을 반복하기 때문에 그리디 알고리즘으로 분류되기도 한다. - 방향/무방향 그래프인지는 상관없다. 다익스트라 알고리즘 동작과정 - 우선순위 큐 사용을 위해 파이썬 heapq를 사용한다. 최소 힙으로 동작하기 때문에 항상 최단 거리를 pop하게 된다. 1. 최단 거리 테이블을 전부 INF(무한)으로 초기화한다. ( 일반적으로는 INF = int(1e9) 이다.)..