11657. 타임머신 (Swift, Python)

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

11657번: 타임머신

 

풀이

 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 문제이다. 1번에서 다른 모든 도시까지의 최단 경로를 구해주면 되는데 이때 걸리는 시간 C가 양수가 아닌 경우가 주어진다. 하나의 노드에서 다른 모든 노드까지의 최단 거리를 구하는 경우 대표적으로 다익스트라 알고리즘을 사용하면 되지만 다익스트라 알고리즘의 경우 간선의 값이 음수가 있는 경우에는 사용할 수 없다.

 그렇기 때문에 이 문제의 경우 음수가 있는 경우에도 사용할 수 있는 벨만 포드 알고리즘을 이용하여 문제를 해결해야 한다. 단순히 벨만 포드 알고리즘을 적용해서 음수 사이클이 있는 경우에는 -1을 출력하면 되고 그렇지 않을 경우에는 다른 도시까지의 최단 거리를 출력해주면 된다.

 

코드

[Swift]

let INF: Int = Int(1e9) // 무한을 나타내는 INF 상수
typealias nodeGraph = (nextNode: Int, cost: Int) // graph에 사용할 typealias
 
// 벨만 포드 알고리즘
func bf(_ start: Int) -> Bool {
    dist[start] = 0
    
    for i in 1...N {
        for cur in 1...N {
            for g in graph[cur] {
                if dist[cur] != INF && dist[g.nextNode] > dist[cur] + g.cost {
                    dist[g.nextNode] = dist[cur] + g.cost
                    
                    // N번째에서 최단 거리가 갱신되는 경우는 음수 사이클이 있음을 나타낸다.
                    if i == N {
                        return true
                    }
                }
            }
        }
    }
    
    return false
}
 
var N: Int = 0
var M: Int = 0
 
if let input = readLine() {
    let inputs = input.split(separator: " ").map { Int($0)! }
    
    N = inputs[0]
    M = inputs[1]
}
 
var graph: [[nodeGraph]] = Array(repeating: [], count: N + 1)
var dist: [Int] = Array(repeating: INF, count: N + 1)
 
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]
        
        graph[a].append((b, c))
    }
}
 
let negativeCycle: Bool = bf(1)
 
if negativeCycle {
    print("-1")
} else {
    for i in 2...N {
        if dist[i] == INF {
            print("-1")
        } else {
            print(dist[i])
        }
    }
}
 

 

[Python]

INF = int(1e9)  # 무한을 나타내는 INF 상수
 
# 벨만 포드 알고리즘
def bf(start):
    dist[start] = 0
 
    for i in range(1, N+1):
        for cur in range(1, N+1):
            for (next_node, cost) in graph[cur]:
                if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                    dist[next_node] = dist[cur] + cost
 
                    # N번째에서 최단 거리가 갱신되는 경우는 음수 사이클이 있음을 나타낸다.
                    if i == N:
                        return True
 
    return False
 
 
if __name__ == '__main__':
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    dist = [INF] * (N+1)
 
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
 
    negative_cycle = bf(1)
 
    if negative_cycle:
        print('-1')
    else:
        for i in range(2, N+1):
            if dist[i] == INF:
                print('-1')
            else:
                print(dist[i])