코딩테스트
경로 추적에 대하여 (다익스트라, 플로이드 )
경로를 탐색해나가는 것에 더 나아가, 경로를 저장한 후 출력하라는 문제들이 종종 있다. 오늘은 어떤 경우에, 어떤식으로 경로를 저장해나가는지 케이스 별로 알아보자 1. 다익스트라,벨만포드 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 문제 11779 번을 풀어보며 알아보자. 이 문제는 다익스트라 문제이지만, 벨만포드도 "경로 추적" 은 동일한 메커니즘으로 돌아간다. 혹시 벨만포드로 된 문제를 풀고 싶다면 ..
