1738. 골목길 (Swift, Python)

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

1738번: 골목길

 

풀이

 민승이네 집(1번)에서 코레스코 콘도(n번)까지 가는데 있어서 최적의 경로를 찾는 문제이다. 가는 경로에 음수가 존재하므로 다익스트라 알고리즘으로는 해결할 수 없고 벨만 포드 알고리즘을 이용해서 해결 가능하다. 기존과의 차이점은 보통 목적지까지 최단 거리를 찾는거였다면 이번 문제는 금품의 양이 최대가 되는 경로를 찾는 것이다.

 하나 주의할 건 기존의 벨만 포드 알고리즘처럼 사이클이 존재한다고 무조건 -1을 출력하면 안된다. 사이클에 해당하는 루트가 n번 노드에 도달할 수 있는 노드인가를 봐야 한다. 그렇기 때문에 사이클이 있을 경우 도착 노드의 dist 값을 INF로 설정해준다. 만약 dist[n]의 값이 INF라면 n번 노드로 가는데 사이클을 통한 루트가 있는 것이므로 -1을 출력해주면 되고 그렇지 않은 경우에는 경로를 출력해 주면 된다.

 

코드

[Swift]

typealias graphElement = (node: Int, cost: Int)
let nINF: Int64 = Int64(Int32.min)
 
// 벨만 포드 알고리즘
func bf(_ start: Int) {
    dist[start] = 0
    
    for i in 0..<n {
        for cur in 1...n {
            for g in graph[cur] {
                let nextNode: Int = g.node
                let cost: Int = g.cost
                
                let nextCost: Int64 = dist[cur] + Int64(cost)
                
                if dist[cur] != nINF && dist[nextNode] < nextCost {
                    dist[nextNode] = nextCost
                    route[nextNode] = cur // next 노드로 가는 전 node를 담아줌
                    
                    if i == n-1 {
                        dist[nextNode] = Int64(Int32.max) // 도착 노드의 금품을 무한으로 설정
                    }
                }
            }
        }
    }
}
 
 
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: [[graphElement]] = Array(repeating: [graphElement](), count: n+1)
var dist: [Int64] = Array(repeating: nINF, count: n+1) // 시작 지점에서 node까지의 최대 금품
var route: [Int] = Array(repeating: 0, count: n+1) // 경로를 담아주기 위한 배열
 
var u: Int = 0
var v: Int = 0
var w: Int = 0
 
for _ in 0..<m {
    if let input = readLine() {
        let inputs = input.split(separator: " ").map { Int($0)! }
        u = inputs[0]
        v = inputs[1]
        w = inputs[2]
        
        graph[u].append((v, w))
    }
}
 
bf(1)
 
var res: [Int] = [n] // 최적의 경로를 담아줄 결과 배열
 
if dist[n] == Int32.max { // n번 노드로 가는데 사이클이 포함되어 있을 경우 -1 출력
    print("-1")
} else { // n번 노드로 가는데 사이클이 포함되어 있지 않을 경우
    var node: Int = n
    
    // n번부터 역으로 res 배열에 담아준다.
    while node != 1 {
        node = route[node]
        res.append(node)
    }
    
    // 뒤집어서 출력
    for i in res.reversed() {
        print(i, terminator: " ")
    }
}
 

[Python]

import math
nINF = -math.inf
 
# 벨만 포드 알고리즘
def bf(start):
    dist[start] = 0
 
    for i in range(n):
        for cur in range(1, n+1):
            for (next, cost) in graph[cur]:
                nextCost = dist[cur] + cost
 
                if dist[cur] != nINF and dist[next] < nextCost:
                    dist[next] = nextCost
                    route[next] = cur # next 노드로 가는 전 node를 담아줌
                    
                    # 사이클일 경우
                    if i == n-1:
                        dist[next] = math.inf # 도착 노드의 금품을 무한으로 설정
 
 
if __name__ == '__main__':
    # 지점의 개수(n), 골목길 개수(m)
    n, m = map(int, input().split())
 
    graph = [[] for _ in range(n+1)]
    dist = [nINF] * (n+1) # 시작 지점에서 node까지의 최대 금품
    route = [0] * (n+1) # 경로를 담아주기 위한 배열
 
    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
 
    bf(1)
    res = [n] # 최적의 경로를 담아줄 결과 배열
 
    # n번 노드로 가는데 사이클이 포함되어 있지 않을 경우
    if dist[n] != math.inf:
        node = n
 
        # n번부터 역으로 res 배열에 담아준다.
        while node != 1:
            node = route[node]
            res.append(node)
 
        # 뒤집어서 출력
        for i in reversed(res):
            print(i, end=' ')
        print()
    else: # n번 노드로 가는데 사이클이 포함되어 있을 경우 -1 출력
        print('-1')