BOJ 1865 웜홀 swift

문제 링크 : https://www.acmicpc.net/problem/1865

 

 

문제 해설

해당 문제는 양방향 간선(도로)와 단방향 간선(웜홀)을 입력받아 음수 사이클이 발생하는 지에 대해 알아보는 문제입니다.

• 양방향 간선(도로)와 단방향 간선(웜홀)을 입력받아 edges에 추가합니다.
• 벨만-포드 알고리즘을 사용하기 위해 거리 배열을 초기화 시킵니다.(이때 거리는 무한입니다.)
• 시작점에서 모든 간선을 N-1번 반복하여 최단거리를 갱신합니다.
• 갱신이 완료되고, 한번 더 실행시켰을 때 갱신이 발생하면 음수 사이클이 존재하는 것입니다.

 

코드

import Foundation

if let tc = Int(readLine()!) {
    for _ in 0..<tc {
        let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let n = input[0], m = input[1], w = input[2]
        var edges: [(Int, Int, Int)] = []

        for _ in 0..<m {
            let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
            let x = input[0], y = input[1], distance = input[2]
            edges.append((x, y, distance))
            edges.append((y, x, distance))
        }

        for _ in 0..<w {
            let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
            let x = input[0], y = input[1], distance = input[2]
            edges.append((x, y, -distance))
        }

        var distance = [Int](repeating: 123_456_789, count: n + 1)
        distance[0] = 0
        for i in 1...n {
            edges.append((0, i , 0))
        }

        // 벨만-포드
        for _ in 1...n {
            for (x, y, dist) in edges {
                if distance[y] > distance[x] + dist {
                    distance[y] = distance[x] + dist
                }
            }
        }

        var negCycle = false
        for (x, y, dist) in edges {
            if distance[y] > distance[x] + dist {
                negCycle = true
                break
            }
        }

        if negCycle {
            print("YES")
        } else {
            print("NO")
        }
    }
}