Algorithm/Shortest Path
![[ACM-ICPC] 화성탐사](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FUXZaS%2Fbtq0MUTkhyG%2FWg7Iiz1VFCvLQjg83nwow0%2Fimg.png)
[ACM-ICPC] 화성탐사
입력 예시 3 3 5 5 4 3 9 1 3 2 7 5 3 7 2 0 1 2 8 0 9 1 1 2 1 8 1 9 8 9 2 0 3 6 5 1 5 7 9 0 5 1 1 5 3 4 1 2 1 6 5 3 0 7 6 1 6 8 5 1 1 7 8 3 2 3 9 8 0 7 6 4 1 5 8 3 2 4 8 3 7 4 8 4 8 3 4 출력예시 20 19 36 초기접근 처음에는 다이나믹 프로그래밍으로 접근했다. 2차원 공간의 왼쪽 위 -> 오른쪽 아래로 가장 빠르게 가는 경우에서 상하좌우로 이동하는 방향에서 좌, 상은 쓸모없는 움직임이라고 생각했다. (한번에 가는것이 돌아가는 것보다 항상 비용이 적을 것이라는 오해) 그래서 우, 하 (오른쪽으로 가기, 아래로 가기) 의 움직임만 고려한 다이나믹 프로그래밍으로 풀었다. 그..
최단경로 알고리즘 풀이법 이론
다익스트라 알고리즘 한 출발노드에서 다른 노드들 까지의 최단거리를 구하는 알고리즘 1. 출발노드 설정 2. 최단거리 테이블 초기화 (자기 자신은 0, 다른 지점까지는 max) 3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다. 5. 3,4번을 반복한다. 구현 코드 import sys input = sys.stdin.readline() INF = int(1e9) n, m = map(int, input().split()) start = int(input()) graph = [[] for i in range(n+1)] visited = [False] * (n+1) distance = [INF] * (n+1..