BOJ-9370 미확인 도착지 Swift

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

내가 푼 풀이

접근방법: 다익스트라

다익스트라로 시작점으로 부터 최단거리를 구한다.

시작점 s에서 목적지 후보들까지의 최단거리를 구하고, 이 최단거리가 g-h 경로를 포함한 최단거리라면 가능한 목적지가 된다.

이 문제는 이해하기도 어려웠는데..

위 사진은 예제코드 두번째의 그래프이다.

목적지 후보 5,6 중 6번만 가능한데 이유는 다음과 같다.

g: 3, h: 1 , 출발지점은 2번이다.

2번-> 5번의 최단거리는 2 - 5:  5 이지만 g-h경로를 지나가는 최단경로가 아니므로 불가능한 목적지가 된다.

2번 ->6번의 최단거리는 2 - 1 - 3 - 6: 6으로 g-h경로를 지나가는 최단경로가 된다. 따라서 6번은 가능한 목적지가 된다.

 

알고리즘 접근은 다음과 같이 했다.

다익스트라를 이용하여 최단거리를 총 3번 구한다.

1. 시작점부터 모든 지점과의 최단거리

2. g지점부터 모든 지점과의 최단거리

3. h지점부터 모든 지점과의 최단거리

 

g -h경로를 통하는 최단거리를 구하려면, g또는 h까지 최단거리를 구해야한다.

주의) g또는 h까지 최단거리가 둘다 같을 수 있기 때문에 2가지 경우의 수를 구해야 한다.

(시작점: s, 도착점: m)

1. s -> g -> h -> m

2. s -> h -> g -> m

 

위 두가지 경우중 하나가 시작점부터 목적지까지의 최단거리와 같다면, g-h경로를 지나간 최단거리가 되므로 가능한 목적지가 된다.

(minS: 시작점에서의 최단거리, minG: g지점에서의 최단거리, minH: h지점에서의 최단거리)

minS[m] = minS[g] + (g-h거리) + minH[m]

minS[m] = minS[h] + (h-g거리) + minG[m]

 

코드로 구현하면 다음과 같다.

import Foundation

// 테스트케이스 수
let T = Int(readLine()!)!

for i in 0..<T {
    // 입력받기
    let input1 = readLine()!.split(separator: " ").map{Int(String($0))!}
    let n = input1[0], m = input1[1], t = input1[2]
    let input2 = readLine()!.split(separator: " ").map{Int(String($0))!}
    let s = input2[0], g = input2[1], h = input2[2]
    var graph = [Int: [(loc: Int, cost: Int)]]()
    var destination = [Int]()
    var answer = [Int]()
    var middleCost = 0
    
    // graph 저장
    for _ in 0..<m {
        let load = readLine()!.split(separator: " ").map{Int(String($0))!}
        // g-h거리 저장
        if (load[0] == g || load[1] == g) && (load[0] == h || load[1] == h) {
            middleCost = load[2]
        }
        if graph[load[0]] == nil {
            graph[load[0]] = [(loc: load[1], cost: load[2])]
        } else {
            graph[load[0]]?.append((loc: load[1], cost: load[2]))
        }
        if graph[load[1]] == nil {
            graph[load[1]] = [(loc: load[0], cost: load[2])]
        } else {
            graph[load[1]]?.append((loc: load[0], cost: load[2]))
        }
    }
    // 목적지 후보 저장
    for _ in 0..<t {
        destination.append(Int(readLine()!)!)
    }
    
    // minS: s지점에서 모든 점까지 최단거리
    // minG: g지점에서 모든 점까지 최단거리
    // minH: h지점에서 모든 점까지 최단거리
    var minS = dijkstra(s: s, n: n, graph: graph)
    var minG = dijkstra(s: g, n: n, graph: graph)
    var minH = dijkstra(s: h, n: n, graph: graph)
    
    // s: 시작점, m: 목적지
    // 두 경우의수 (s - g - h - m)의 최단거리 , (s - h - g - m)의 최단거리 가 (s - m)최단거리와 같다면 가능한 목적지
    for m in destination {
        let sumG = minS[g] + middleCost + minH[m]
        let sumH = minS[h] + middleCost + minG[m]
        
        if sumG == minS[m] || sumH == minS[m] {
            answer.append(m)
        }
    }
    // 오름차순으로 출력
    answer.sort{$0 < $1}
    print(answer.map{String($0)}.joined(separator: " "))
}

// 다익스트라
func dijkstra(s: Int, n: Int, graph: [Int: [(loc: Int, cost: Int)]]) -> [Int] {
    var needVisit = [(loc: s, cost: 0)]
    var idx = 0
    var min = Array(repeating: 2000000000, count: n+1)
    min[s] = 0
    
    while idx < needVisit.count {
        let node = needVisit[idx]
        idx += 1
        if graph[node.loc] == nil { continue }
        for i in graph[node.loc]! {
            let dist = i.cost
            if node.cost + dist < min[i.loc] {
                min[i.loc] = node.cost + dist
                needVisit.append((loc: i.loc, cost: min[i.loc]))
            }
        }
    }
    return min
}