one Book a Day

조건이 있는 다익스트라. 다익스트라까지는 구현이 쉬웠지만 검문소 하나하나 거는게 생각보다 빡빡했다. 결국 최소거리 path를 구해서 그 도로들만 조사하고 또 이거저거 필요없는 조건들 줄여서야 겨우 시간 통과. 다른분들 풀이보니 아예 최소 이동 도로만 조사하셨던데 그걸 의도한게 맞을듯. 여튼 나는 그냥 모든 지점에 대해 최소로 이동되는 도로들만 조사했다. import sys input = sys.stdin.readline from heapq import heappop,heappush # 가중치 있는 그래프. # 최소 시간. 양수. # 경찰 도로 검문(간선 가중치 무한대).(탈출 지연) # 1진입 N탈출. -> 다익스트라. # 경찰이 도로를 막았을때 지연시킬 수 있는 최대시간을 정수로 출력. # 지연효과없으..

최단 경로 알고리즘. 주요 알고리즘 BFS (완전탐색 알고리즘) 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다 다익스트라 알고리즘 (Dijkstra Algorithm) 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm) 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 전체 쌍 최단 경로 문제, 다수출발, 단일도착 하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우 A*알고리즘이 적합하다. 다익스트라 특정 노드에서 다른 모든 노드로 가는 최단경로를 갱신. 음의 간..

다익스트라 알고리즘 최단경로를 찾는 알고리즘 중 양의 가중치만이 있는 그래프만을 취급 특정 위치에서 도착위치의 최단경로를 찾는 알고리즘(모든경로의 최단경로를 구하지는 않는다. 그리디하게 정점을 선택해 방문. 선택한 정점의 인접정점 중 방문되지 않은 것들에 대해 최단경로를 구해가며 도착지점에 도달. 배열에 각각 노드에 접근 시 가중치 합을 저장하며 지나간다. 0번 노드에서 출발해서 방문하지 않은 인접한 노드 중에 가중치가 가장 적은 노드에 대해 방문한다. 현재 그리디하게 선택한 경로의 가중치 합이 나중에 최단 경로가 아닐 수도 있으니 배열에 가중치의 합들을 저장하며 지나간다 1번 노드에서 인접한 노드 중 가중치가 제일 작은것은 4번이다. 이 때, 비교해봐야하는 것은 0번 노드에서 4번노드로 가는 경로 중 ..