[백준/Swift] 11404: 플로이드 PS일지.

문제

11404번: 플로이드

간단한 문제 요약

 n개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. 각 버스는 사용시 필요한 비용이 있다. 모든 도시 쌍에 대해서 도시 A -> B로 가는 최단 경로를 구하시오!!

 

고려해야 할 사항

• 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다!!

 문제에서 주여졌습니다. 즉, 문제 input에서 A -> B로 가는 비용 10 을 입력 받았는데 A -> B로 가는 비용 5 를 추가로 입력 받을 수 있다는 것입니다. 이 둘 중에서 최소 값을 찾아서 넣어야 합니다.

문제 풀이, 했갈렸던 점

 플로이드 알고리즘은 v -> w 로 가는 경우에서 특정한 도시 k를 지났을 때 기존에 갈 수 있는 v -> w 비용보다 단축될 수 있는가?를 체크하고 갱신해나가는 알고리즘 입니다.

// v : 시작 정점 , w : 도착 정점, k : 특정한 정점

A[v][w] = min(A[v][w],A[v][k] + A[k][w]) 

이때 주의할 점은 제 코드에선 visited를 Int.max로 두었기 때문에 Int.max + 자연수 or Int.max의 경우 컴파일 에러가 발생합니다. 사전에 체크해야 합니다.

 

 최악의 경우 간선수가 엄청 많습니다. 플로이드는 for 구문 3번 사용해서 O(V^3)의 시간복잡도가 걸립니다. 한가지 실수했던 점은 문제 풀 때 문제 인풋에서 시작 도시에서 도착 도시를 가는 경우가 1개가 아닐 수 있다는 것을 스킵 했었습니다... (문제 끝까지 보는 습관을 들여야겠습니다.)

코드

let vCnt = Int(readLine()!)!
let eCnt = Int(readLine()!)!
var visited = Array(repeating: Array(repeating: Int.max, count: vCnt), count: vCnt)
for i in 0..<vCnt { visited[i][i] = 0 }
(0..<eCnt).forEach { _ in
    let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
    let (s,e,c) = (input[0]-1,input[1]-1,input[2])
    visited[s][e] = min(c,visited[s][e])
}
for k in 0..<vCnt {
    for v in 0..<vCnt {
        for w in 0..<vCnt {
            if visited[v][k] == Int.max || visited[k][w] == Int.max {
                continue
            }
            visited[v][w] = min(visited[v][w], visited[v][k]+visited[k][w])
        }
    }
}
visited.forEach{print($0.reduce(""){"\($0)\($1==Int.max ? 0 : $1) "})}