백준 - 플로이드 (11404)

let n = Int(readLine()!)!
let m = Int(readLine()!)!

// 인접 행렬 구현
var graph = Array(repeating: Array(repeating: 10000000, count: n+1), count: n+1)
// 자기 자신으로 가는 비용은 0으로
for i in 1...n {
    graph[i][i] = 0
}

// 비용 입력받기
for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[input[0]][input[1]] = min(graph[input[0]][input[1]], input[2])
}

// 플로이드 와샬 알고리즘 실행
for k in 1...n { // 경유지
    for i in 1...n { // 시작 도시
        for j in 1...n { // 도착 도시
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        }
    }
}

// 정답 출력
var answer = ""
for i in 1...n {
    for j in 1...n {
        answer += "\(graph[i][j] == 10000000 ? 0 : graph[i][j]) "
    }
    answer += "\n"
}

print(answer)

플로이드 와샬 알고리즘을 구현하는 기본적인 문제였다.

주의할 점

• 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
  • 작은 값이 올 때만 distance 값이 갱신될 수 있도록 해야 한다.
• 두 도시로 가는 경로가 없을 때는 충분히 큰 값을 넣는다.
  • Int.max 로 설정했더니 오버플로우가 발생해서 10000000 으로 설정해주었다. 1000001 으로 설정하면 98% 정도 와서 WA가 뜬다.. -_-