[Swift] 백준 타임머신 11657

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

 

 

1. 문제이해

• 한 도시에서 출발하여 다른 도시에 도착하는 버스가 있다.
• N개의 도시(노드), M개의 버스(간선)
• 입력 형태는 A, B, C
  • A는 시작 도시, B는 도착 도시, C는 버스를 타고 이동하는데 걸리는 시간
  • C는 양수가 아닌 음수일 수도 있다.(타임머신)

• 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하자 - 요구 출력
• 만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 -1 출력 (음의 사이클)
• 1번 도시에서 출발해서 모든 나머지 도시마다 가장 빠른 시간을 출력하되 해당 도시로 가는 경로가 없다면 -1 출력

 

2. 접근방법

• 가중치에 음수가 있으므로 밸만-포드 알고리즘 사용하기
• 밸만-포드 알고리즘 https://ko.wikipedia.org/wiki/벨먼-포드_알고리즘
  • 그래프 형태에서 최단경로를 찾는 알고리즘
  • 한 정점에서 다른 모든 정점으로 가는데 걸리는 최소비용을 구할 수 있음
  • 음수인 가중치에 대해서도 활용 가능

밸만-포드 알고리즘 프로세스

1. 그래프 초기화
   • 예시) edges[ [(도착노드, 이동시간), (도착노드, 이동시간)], [(도착노드, 이동시간)], [(도착노드, 이동시간)], [(도착노드, 이동시간)], ]
   • [(2, 3), (3, 2)] 1번 노드 [(3, 3)] [] [(2, -4)]
   • 1번 노드에서 나머지 노드들까지 걸리는 시간 (distance[INF] * N)
   • distance[0] = 0 → 시작 노드는 0으로 초기화
2. 최소비용 구하기
   1. Distance[index] != INF
   • N-1번 반복
     • 최단 경로 그래프에서 노드가 N개 일 때 간선은 최대 N-1만 포함하기 때문
   • distance[nextNode] > distance[curNode] + cost일 때
     • distance[nextNode] = distance[curNode] + cost
3. 음의 사이클 여부 구하기
   • N-1 반복 이후에 distance[nextNode] > distance[curNode] + cost 조건이 참인 경우 음의 사이클이 존재

3. 코드

import Foundation

func solution(){
    var input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let N = input[0]
    let M = input[1]
    var edges = Array(repeating: [(Int,Int)](), count: N)
    var result = Array(repeating: Int.max, count: N)

    
    for _ in 0..<M{
        input = readLine()!.split(separator: " ").map{Int(String($0))!}
        edges[input[0]-1].append((input[1]-1, input[2]))
    }
    
    result[0] = 0 // 시작 노드는 0으로 초기화

    // 최소비용 구하기
    for _ in 0..<N-1{ // N-1번 반복
        for cur in 0..<edges.count{
            for edge in edges[cur]{
                let next = edge.0
                let cost = edge.1
                
                if result[cur] != Int.max, result[next] > result[cur] + cost{
                    result[next] = result[cur] + cost
                }
            }
        }
    }
    
    // 음의 사이클 여부
    for cur in 0..<edges.count{
        for edge in edges[cur]{
            let next = edge.0
            let cost = edge.1
            
            if result[cur] != Int.max, result[next] > result[cur] + cost{
                print("-1")
                return
            }
        }
    }
    
    for i in 1..<N{
        if result[i] == Int.max{
            print("-1")
        }else{
            print(result[i])
        }
    }
}
solution()