만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 11404 플로이드

23 Jun 2021

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

문제 제목부터 플로이드를 사용하라 말해주는 문제이다. 똑같이 도시 간의 이동 비용을 구하는데 모든 도시에서 다른 모든 도시로의 비용을 구하는 것이 특징이다. 다익스트라를 사용해서 일일히 구해도 되나 시간 상 느리기 때문에 플로이드 와샬 알고리즘을 연습해보자.

for i in 1...n {
    for j in 1...n {
        if j == i {continue}
        for k in 1...n {
            if k == i || k == j {continue}
            Edge[j][k] = min(Edge[j][k], Edge[j][i] + Edge[i][k])
        }
    }
}

코드는 앞에서 봐서 알겠지만 여기서는 cycle이 존재하지 않기 때문에 i와 j가 같은 지점은 건너뛰게 했다. 참고로 i, j, k의 for문 순서는 알고리즘에 영향을 주지 않는다.

let n = Int(readLine()!)!
let m = Int(readLine()!)!
var Edge:[[Int]] = Array(repeating: Array(repeating: 10_000_001, count: n+1), count: n+1)
for _ in 1...m {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    let from = line[0], to = line[1], cost = line[2]
    Edge[from][to] = min(Edge[from][to], cost)
}

for i in 1...n {
    for j in 1...n {
        if j == i {continue}
        for k in 1...n {
            if k == i || k == j {continue}
            Edge[j][k] = min(Edge[j][k], Edge[j][i] + Edge[i][k])
        }
    }
}

var str = ""
for i in 1...n {
    for j in 1...n {
        str += "\(Edge[i][j] > 10_000_000 ? 0 : Edge[i][j]) "
    }
    str += "\n"
}
print(str)

Related posts