[백준/Swift] 11404번: 플로이드

 

https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

다익스트라는 시작점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

플로이드-워셜은 모든 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

 

모든 노드 간의 최단 거리를 구해야 하므로 2차원 인접 행렬

• 여러 라운드로 구성된다.
• 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고 더 짧은 길이를 선택해 줄이는 과정반복

 

구현

각 라운드 별

    각 노드별 모든 거리 살피면서

        라운드 노르를 중간 노드로 삼을 때와 아닐 때를 비교하면서

            min value 갱신

            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

 

 

이 문제에서 주의할 것

 

- 양방향 간선이 아님

- 하나의 경로에 여러 버스가 있을 수 있음

 

import Foundation

/*
 n개의 도시. -> 정점 개수
 한 도시에서 출발해 다른 도시에 도착하는 m개의 버스 -> 간선 개수
 각 버스는 한 번 사용할 때 필요한 비용
 모든 도시 쌍에대해서 A에서 B로 가는데 필요한 최솟값 구하기
 */

//input
let n = Int(readLine()!)! //도시 n개 -> 정점 개수
let m = Int(readLine()!)! //버스 m개 -> 간선 개수
var adj = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: n+1)
let INF = 987654321
for _ in 0..<m {
    let vertex = readLine()!.split(separator: " ").map{ Int(String($0))! }
    adj[vertex[0]][vertex[1]] = adj[vertex[0]][vertex[1]] == 0 ? vertex[2] : min(adj[vertex[0]][vertex[1]], vertex[2])
}

for i in 1...n {
    for j in 1...n {
        if i == j { //자기 자신
            adj[i][j] = 0
        }else if adj[i][j] == 0 { //가는 길이 없다는 뜻
            adj[i][j] = INF
        }
    }
}

//floyd algorithm
for k in 1...n { //라운드 n번 진행
    for i in 1...n {
        for j in 1...n {
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
        }
    }
}
for i in 1...n {
    for j in 1...n {
        if adj[i][j] == INF {
            print(0, terminator: " ")
        }else {
            print(adj[i][j], terminator: " ")
        }
    }
    print("")
}