11404. 플로이드 (Swift, Python)

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

11404번: 플로이드

 

풀이 

 플로이드 워셜 알고리즘을 적용하는 문제. 모든 도시에서 다른 모든 도시까지의 최단거리를 구해준다.

 간단하게 플로이드 워셜 알고리즘을 적용하면 되는데 문제에서 주어진 '시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.'만 주의하면 된다. a에서 b로 가는 도시의 노선이 여러개 주어질 수 있는데 그 중 가장 적은 비용이 드는 노선을 배열에 설정해줘야 한다. 

 

코드

[Swift]

 

let INF: Int = Int(1e9)
 
var N: Int = 0 // 도시의 개수
var M: Int = 0 // 버스의 개수
 
// 도시 개수 입력
if let input = readLine() {
    N = Int(input)!
}
 
// 버스 개수 입력
if let input = readLine() {
    M = Int(input)!
}
 
// a에서 b로 가는데 필요한 비용
var graph: [[Int]] = Array(repeating: Array(repeating: INF, count: N + 1), count: N + 1)
 
// i에서 i의 경우 0으로 설정
for i in 1...N {
    graph[i][i] = 0
}
 
// 버스 정보 입력
for _ in 0..<M {
    if let input = readLine() {
        let inputs = input.split(separator: " ").map { Int($0)! }
        let a: Int = inputs[0]
        let b: Int = inputs[1]
        let c: Int = inputs[2]
        
        // 문제에서 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다고 주어짐
        // 그렇기 때문에 a에서 b로 가는 노선이 여러개 주어질 경우 graph 배열에 최솟값을 넣어주도록 설정
        graph[a][b] = min(graph[a][b], c)
    }
}
 
// 플로이드 워셜 알고리즘 수행
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])
        }
    }
}
 
// 출력
for i in 1...N {
    for j in 1...N {
        if graph[i][j] == INF {
            print(0, terminator: " ")
        } else {
            print(graph[i][j], terminator: " ")
        }
    }
    print()
}
 

 

[Python]

 

INF = int(1e9)
 
if __name__ == '__main__':
    n = int(input()) # 도시의 개수
    m = int(input()) # 버스의 개수
 
    # a에서 b로 가는데 필요한 비용을 담아두는 graph 리스트
    graph = [[INF] * (n+1) for _ in range(n+1)]
 
    # i에서 i로 가는 비용은 0으로 설정
    for i in range(1, n+1):
        graph[i][i] = 0
    
    # 버스 노선 정보 입력
    for _ in range(m):
        a, b, c = map(int, input().split())
 
        # 문제에서 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다고 주어짐
        # 그렇기 때문에 a에서 b로 가는 노선이 여러개 주어질 경우 graph 리스트에 최솟값을 넣어주도록 설정
        if c < graph[a][b]:
            graph[a][b] = c
    
    # 플로이드 워셜 알고리즘 수행
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                graph[i][j] = min(graph[i][j] , graph[i][k] + graph[k][j])
    
    # 출력
    for i in range(1, n+1):
        for j in range(1, n+1):
            if graph[i][j] == INF:
                print(0, end=' ')
            else:
                print(graph[i][j], end=' ')
        print()