ym_coding

출처:: 코딩테스트 교재 최단경로알고리즘 분류:: 다익스트라알고리즘 1. 문제 이해 및 해결과정 입력 3 2 1 1 2 4 1 3 2 출력 2 4 첫 째줄에 도시의개수 N 통로의 개수 M 메시지를 보내고자 하는 도시 C가 있다. 둘째 줄 부터 M+1 번째 줄에 걸쳐서 통로에 대한 정보 X Y Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며 메시지가 전달되는 시간이 Z라는 의미이다. 첫째줄 도시 C에서 보낸 메시지를 받는 도시의 총개수와 총 걸리는 시간을 공백으로 구분하여 출력한다. 2. 풀이방법 import sys from queue import PriorityQueue N, M, C = map(int , input().split()) dic_arr = {} weigh..

가장 빠른길 찾기 ? 한 지점에서 다른 특정 지점까지의 최단경로를 구해야 하는 경우를 뜻한다. 크게 세가지가 있다. 1) 다익스트라 알고리즘 2) 벨만 포드 알고리즘 3) 플로이드 워셜 알고리즘 가장 중요한 것은 다익스트라 알고리즘과 플로이드 워샬 알고리즘이다. 두가지만 파악을 해도 코딩테스트 수준에서 최단경로 문제는 어렵지 않게 해결 할 수 있다. 1. 다익스트라 알고리즘 GPS 소프트웨어의 가장 기초적 알고리즘으로 채택된다. 다익스트라 알고리즘은 그리디 알고리즘을 사용한다고 생각하면 된다. 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다. 여기서 또 필요한 알고리즘은 Priority Queue 우선순위 큐이다. 가장 작은 간선의 수를 먼저 실행시켜야 하기 때문이다. ..