플로이드 (2) 썸네일형 리스트형 [Algorithm] 플로이드 와셜(Floyd-Warshall) 개념 뿌수기!! 1. What is Floyd Warshall? 플로이드 와샬 알고리즘은 '모든' 정점 사이의 최단 경로를 구할 때 사용하는 알고리즘 입니다. 한 정점->인접한 다른 정점으로 갈 때 비용을 전부 2차원 배열에 저장합니다. 모든 정점을 포문으로 탐색하게 되는데 이때 특정 한 정점일 때 해당 정점을 거쳐서 갈 수 있는 경로가 원래 2차원 배열에 저장된 경로의 비용보다 낮다면 2차원 배열의 cost를 갱신합니다. 2. Floyd Warshall's algorithm 인접 정점 간 갈 수 있는 비용을 2차원 배열 visited에 저장했다고 가정한다면 점화식은 visited[v][w] = min(visited[v][w], visited[v][k] + visited[k][w])입니다. v : 시작 정점 w : 도착.. [백준/Swift] 11404: 플로이드 PS일지. 문제 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 간단한 문제 요약 n개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. 각 버스는 사용시 필요한 비용이 있다. 모든 도시 쌍에 대해서 도시 A -> B로 가는 최단 경로를 구하시오!! 고려해야 할 사항 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다!! 문제에서 주여졌습니다. 즉, 문제 input에서 A -> B로 가는 비용 10 을 입력 받았는데 A -> B로 가는 비용 5 를 추가로 입력 받을 수 있다는 것입.. 이전 1 다음
