백준 1865번 웜홀 - SWIFT

문제

---

때는 2020년, 백준이는 월드나라의 한 국민이다.

월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.)

웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다.

웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다.

한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다.

여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

 

 

입력

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다.

그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), 도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다.

그리고 두 번째 줄부터 M+1번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다.

S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다.

그리고 M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다.

T는 10,000보다 작거나 같은 자연수 또는 0이다.

두 지점을 연결하는 도로가 한 개보다 많을 수도 있다.

지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

 

출력

TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

 

문제 링크

 

 

풀이

---

백준 11657번 풀이와 거의 동일하다.

하지만 11657번 문제와는 약간 다른 점이 하나 있다면, 11657은 최단 거리가 있을 경우 최단 거리를 출력하라고 했지만, 1865번은 음의 싸이클이 있냐 없냐만 찾으면 된다.

 

벨만-포드 알고리즘이란?

가중치가 있는 그래프에서 최단 경로 문제를 푸는 알고리즘이다.

최단 경로 문제라고 하면 다익스트라와 같은 작업을 수행하고, 심지어는 다익스트라가 더 빠르기까지 하다.

하지만 벨만-포드 알고리즘의 의의는 다익스트라 알고리즘이 처리하지 못하는 음수인 간선을 처리할 수 있다는 것이다.

그래서 음수인 간선이 등장하는 경우에는 벨만-포드 알고리즘을 사용한다.

V와 E가 각각 그래프에서 꼭짓점과 변의 개수라고 한다면, 벨먼-포드 알고리즘의 실행시간은 O(|V| |E|)이다.

 

벨만-포드 알고리즘의 동작

벨만-포드에서 중요한 부분

벨만-포드 알고리즘에서 가장 중요시 해야할 부분은 음의 싸이클이다.

벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 값이 더 작은 값이 나오면 갱신하는 식으로 진행된다.

그런데 음의 싸이클이 등장하게 되면, 한 번 순회를 돌 때마다 값이 계속 작아져서 무한히 갱신하게 된다.

그래서 우리는 순회 횟수를 V - 1로 제한을 한다. (여기서 V는 정점 개수다.)

왜냐하면 시작 정점에서 특정 정점까지 도달하기 위해 거쳐가는 최대 간선 수는 V - 1 개이기 때문이다.

따라서 경로에 V번째 간선이 추가되면 싸이클에 진입했다고 판단한다.

그러면 본격적으로 동작을 보자.

 

벨만-포드의 작동

왼쪽은 간선이 표시된 그래프이고, 오른쪽은 최단 거리를 표시할 그래프이다.

1. 1번 부터 시작할 것이므로, 1번 정점의 최단 거리는 0으로 두고 나머지 정점은 INF로 초기화해준다.▼

 

 

2. 1번 노드부터 모든 간선을 체크해본다.

1번에서 2번으로 간다고 했을 때, 2번 노드에 할당된 값이 INF보다 0 + 4가 더 작으므로 갱신해준다.▼

 

 

1번에서 3번으로 간다고 했을 때, 3번 노드에 할당된 값이 INF보다 0 + 3이 더 작으므로 갱신해준다.▼

 

 

다음엔 2번에서 3번으로 가는 경우를 체크해보면, 4 - 1은 3이랑 같으므로 갱신하지 않는다.

마찬가지로 3번에서 1번으로 가는 경우, 3 - 2는 0보다 크므로 갱신하지 않는다.▼

 

 

2번에서 5번 노드로 간다고 했을 때, 4 - 5 는 INF보다 작으므로 갱신해준다.

3번에서 4번 노드로 간다고 했을 때, 3 + 2 는 INF보다 작으므로 갱신해준다.▼

 

 

나머지 간선인 5번에서 2번과 4번에서 5번을 보면, 5번에서 2번 노드로 갈 시 값이 더 작아지므로 갱신해준다.

하지만 4번에서 5번으로 가는 경우는 -1이 5 + 3보다 더 작으므로 갱신해주지 않는다.▼

 

 

이렇게 모든 간선에 대한 순회가 1회 끝났다.

하지만 앞서 말한대로 음의 싸이클이 존재하는 경우 순회를 다시 한 번 더 돌리게 되면 값이 갱신되어 변하게 된다.

그리고 여러번 순회를 돌려주는 다른 이유는 간선 순회 순서에 따라 값이 갱신되지 않는 경우 다음 순회에서 그 값이 싸이클이 아니더라도 갱신되는 경우도 있기 때문이다.

 

일단 V - 1회를 돌려주기로 했으니, 같은 방식으로 나머지 3회를 마저 돌려보면 아래 처럼 변한다.▼

 

 

딱 보기에도 전체적으로 값이 다 줄었다.

 

보면 알겠지만 2번과 5번 사이에 음의 싸이클이 형성되어있기 때문에 값이 계속해서 줄어들어 다른 값들에도 영향을 준 것이다.

 

그럼 이제 음의 싸이클 판별을 해보자.

 

 

3. 순회를 한 번 더 돌려서 값이 변하는 지 체크해본다.

만약 한 간선이라도 값이 변하게 된다면, 그건 음의 싸이클이라는 증거다.

음의 싸이클이 없다면, 다른 값들의 갱신은 이루어지지 않는다.

위의 예시를 기준으로 순회를 돌면서 값이 바뀌는 부분을 체크해보면 세 군데가 바뀔 수있다고 나온다.▼

 

 

값이 갱신될 수 있으므로 이 그래프에서의 최단거리는 구할 수 없다.

하지만 만약 값이 갱신될 수 없다고 판별이 되면, V - 1번째 순회의 결과가 최단거리가 된다.

 

 

문제에 적용

이 문제는 논란이 많았다.

이 문제를 푼 사람들의 코드는 두 가지 종류의 코드로 나뉘었는데, 코드 유형은 아래와 같다.

1. 방문하지 않은 정점에 대해서도 최단거리 갱신
2. 방문한 정점에 대해서만 최단거리 갱신

둘 중 한 코드가 무조건 맞다는 건 아니지만, 재채점이 되었을 때, 1번의 경우 대체로 정답처리가 되었고, 2번의 경우 대체로 오답처리가 되었다.

 

왜 그런지를 알아보자.

첫번째 유형의 경우를 보면, 이렇게 생각할 수 있다.

 

 

"방문 못하는 정점까지 최단 거리를 갱신해 줄 필요가 있나? 어차피 못가는 정점인데?"

 

 

하지만 여기엔 엄청난 함정이 있다.

위에 처럼 생각한 사람은 출발 정점이 1번 정점이라고 생각했을 것이다.

하지만 문제에는 어디에도 1번이 출발이라고 한 적이 없다.

따라서 모든 정점이 출발 정점이 될 수 있고, 그 중 어디서든 음의 싸이클이 발견되기만 한다면 시간이 줄어든 채로 시작정점으로 되돌아 올 수 있다느 것이다.

 

아래의 예시를 보면 이해가 빠를 것이다.▼

 

 

위의 예시를 보면 두번째 유형의 코드가 틀리는 경우가 쉽게 떠오를 것이다.

1번 정점에서는 방문 못하는 정점인 3번과 4번이 음의 싸이클을 이루지만, 방문한 정점에 대해서만 최단거리를 갱신하기 때문에 음의 싸이클을 찾을 수 없다는 것이다.

 

그렇다면 2번 유형으로 풀었다면 어떻게 고치면 될까?

 

모든 정점을 시작 정점으로 두고, 하나씩 체크해보면 된다.

 

1번 정점이 시작 정점일 때, 2번 정점이 시작 정점일 때 ... N번 정점이 시작 정점일 때.

이렇게 체크해보면 2번 유형의 풀이로도 정답을 얻어낼 수 있다.

필자는 2번 유형으로 모든 정점을 체크해보는 식으로 풀었다.

 

 

Swift 코드

var answer = ""
let INF = 2000000000
for _ in 0..<Int(readLine()!)! {

    let NMW = readLine()!.split(separator: " ").map { Int(String($0))! }
    let N = NMW[0], M = NMW[1], W = NMW[2]
    var road = [(Int, Int, Int)]()
    var flag = false

    for _ in 0..<M {
        let SET = readLine()!.split(separator: " ").map { Int(String($0))! }
        road.append((SET[0], SET[1], SET[2]))
        road.append((SET[1], SET[0], SET[2]))
    }
    for _ in 0..<W {
        let SET = readLine()!.split(separator: " ").map { Int(String($0))! }
        road.append((SET[0], SET[1], -SET[2]))
    }

    for i in 1...N {
        if bellmanFord(i, road, N, M * 2 + W) {
            flag = true
            answer += "YES\n"
            break
        }
    }
    if !flag {
        answer += "NO\n"
    }
}

print(answer)

func bellmanFord(_ start: Int, _ road: [(Int, Int, Int)], _ N: Int, _ roadcount: Int) -> Bool {
    var dist = Array(repeating: INF, count: N + 1)
    var flag = false
    dist[start] = 0

    for _ in 1..<N {
        flag = false
        for j in 0..<roadcount {
            let u = road[j].0
            let v = road[j].1
            let w = road[j].2
            if dist[u] != INF && dist[u] + w < dist[v] {
                dist[v] = dist[u] + w
                flag = true
            }
        }
        if !flag {
            break
        }
    }
    if flag {
        for j in 0..<roadcount {
            let u = road[j].0
            let v = road[j].1
            let w = road[j].2

            if dist[u] != INF && dist[u] + w < dist[v] {
                return true
            }
        }
    }
    return false
}