목록11404 (1)

JINWOOJUNG

[ DP - 11404 ] 플로이드(C++)

접근법 최단경로 찾기에 적용 가능한 Dynamic Programming Algorithm이 바로 Floyd(플로이드)이다. 문제를 보면 특정 도시에서 다른 도시로 가는 서로다른 비용을 가지는 버스가 존재하고, 특정 도시에서 다른 도시로 가는 최소 비용을 구하는 문제이다. 따라서 주어진 문제(경로에 따른 비용)에 대하여 하나 이상의 많은 해가 존재할 때, 최적의 해답을 찾아야 하는 최적화 문제이다.  우리는 주어진 정보 중 출발 도시와 도착 도시 사이의 최소 cost를 원소로 가지는 인접 행렬식 $W$를 포현할 수 있다. 예를들어, $W[i][j]& 는 $i$에서 $j$로 가는 최소 비용을 의미한다. 만약 $i$에서 $j$로 가는 버스가 없다면, 구해야 하는 것은 최소 비용이기 때문에 무한대로 표현하고, ..
백준 2024. 5. 23. 17:52
이전 Prev 1 Next 다음