[백준/Swift] 1504: 특정한 최단 경로

문제

1504번: 특정한 최단 경로

간단한 문제 요약

 방향성 없는 그래프가 주어진다. 1->N 정점으로 최단 거리로 이동하려고 한다. 이때 문제에서 주어진 임의의 두가지 정점은 반드시 통과해야 한다. 물론 한번 이동했던 정점, 간선을 다시 이동할 수 있다.(최단 경로로 이동한다는 전제하에) 1 -> N까지 최단 경로를 갈 때 반드시 임의의 두 정점 v1, v2를 거쳐 최단 경로를 가는 경로 길이를 출력 해야한다.

 

고려해야 할 사항

• v1 -> v2로 가는 경우가 없을 수도 있습니다. 이땐 -1을 출력해야 합니다.
• v1 -> N으로 가는 경우가 없을 수도 있고 v2 -> N으로 가는 경우가 없을 수도 있습니다. 이때도 -1을 출력해야 합니다.
• 문제의 input vertex들은 1부터 시작합니다. ( 저는 0부터 시작하도록 하는게 편해서,,)

문제 풀이, 했갈렸던 점

 "최단 경로를 탐색 할 때 어떻게 특정 구간 방문을 체크하면서 도착 지점까지의 최단 경로를 구할까?" 새로웠던 문제 였습니다. 다익스트라는 한 정점에서 다른 정점까지 갈 수 있는 최단 경로를 구하는 알고리즘 입니다. 이를 이용해서 거쳐야 하는 특정 정점 v1, v2에서 각각의 경로에 대한 최단 경로 탐색을 진행했습니다.

 

 총 거쳐야 할 정점은 1번 vertex, v1 vertex, v2 vertex, N vertex 입니다. 그리고 한번 이동했던 정점, 간선을 다시 거쳐 갈 수 있다는 글이 주어졌습니다.(최단 경로 전제) 

1. 1번 정점 -> v1까지 갈 때의 최단 경로 | v1 -> v2까지 갈 때의 최단 경로 | v2 -> N까지 갈 때의 최단 경로

2. 1번 정점 -> v2까지 갈 때의 최단 경로 | v2 -> v1까지 갈 때의 최단 경로 | v1 -> N까지 갈 때의 최단 경로

이 두가지 경우가 있다고 판단 했습니다. 1번 정점을 start 정점으로 한 다익스트라 알고리즘을 적용시킬 때

1 -> 2 

1 -> 3

...

1 -> v1

1 -> v2

...

1 -> N

까지 각각의 정점에 대한 최단 경로를 구할 수 있습니다. 1->N까지의 최단 경로는 v1, v2를 거치지 않을 수 있기에 패스!!

1 -> v1까지 갔을 때의 최단 경로, 1-> v2까지 갔을 때의 최단 경로를 구할 수 있습니다.

 

이제 v1 정점을 start 정점으로 한 다익스트라 알고리즘을 적용시키면 

v1 -> 1 

...

v1 -> v2

...

v1 -> N 

대표적으로 이렇게 최단 경로 알고리즘을 구할 수 있습니다. v1 -> v2 최단 경로나 v2 -> v1 최단 경로 cost는 같기에 v2일때 v1에 대한 최단 경로를 구하지 않아도 됩니다.

 

마지막으로 

v2일때 start 정점으로 시작해 구할 수 있는 최단 경루 중 N 정점에 도착 했을 경우를 구하면 됩니다.

v2 -> N

 

위에서 구한 1. 2. 경우의 수 중 가장 적은 비용을 갖는 경로가 v1, v2를 거친 최단 경로가 됩니다. 

 

78%에서 한 2번 틀리면서 위에서 언급한 고려해야 할 사항과 같은 경우로 틀릴 수 있다는 것을 알게 되었습니다.

(Int.max + Int.max  -> 런타임에러..)

코드

import Foundation

struct Heap<T> where T: Comparable {
    private var list = [T]()
    let isLeftSmall: (T,T)->Bool
    init(isLeftSmall: @escaping (T, T) -> Bool) {
        self.isLeftSmall = isLeftSmall
    }
    init(){
        self.init(isLeftSmall: <)
    }
}
extension Heap {
    var count: Int {
        return list.count
    }
    var isEmpty: Bool {
        return list.isEmpty
    }
    var peek: T? {
        return list.first
    }
}
extension Heap {
    mutating func insert(_ element: T) {
        var idx = list.count
        list.append(element)
        while idx > 0 && isLeftSmall(list[idx],list[(idx-1)/2]) {
            list.swapAt(idx, (idx-1)/2)
            idx = (idx-1)/2
        }
    }
    mutating func delete() -> T? {
        guard !isEmpty else {
            return nil
        }
        guard count != 1 else {
            return list.removeFirst()
        }
        var idx = 0
        let element = list.first!
        list.swapAt(idx, count-1)
        _ = list.popLast()
        while idx < count {
            let (left,right) = (idx*2+1,idx*2+2)
            if right < count {
                if isLeftSmall(list[left],list[right]) && isLeftSmall(list[left],list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else if isLeftSmall(list[right],list[idx]) {
                    list.swapAt(right, idx)
                    idx = right
                } else {
                    break
                }
                
            } else if left < count {
                if isLeftSmall(list[left],list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else {
                    break
                }
            } else {
                break
            }
        }
        return element
    }
}

struct Node {
    let vertex: Int
    let cost: Int
    
}
extension Node: Comparable {
    static func <(lhs: Node, rhs: Node) -> Bool {
        return lhs.cost < rhs.cost
    }
    static func ==(lhs: Node, rhs: Node) -> Bool {
        return lhs.vertex == rhs.vertex
    }
}

//MARK: - Properties
let ve = readLine()!.split{$0==" "}.map{Int(String($0))!}
let nodeCount = ve[0]
let edgeCount = ve[1]
var graph = Array(repeating:[Node](),count:nodeCount)
(0..<edgeCount).forEach { _ in
    let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
    let (s,e,c) = (input[0] - 1,input[1] - 1,input[2])
    graph[s].append(Node(vertex: e, cost: c))
    graph[e].append(Node(vertex: s, cost: c))
}
let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (v1,v2) = (input[0]-1,input[1]-1)

func dijkstra(_ start: Int, visited: inout [Int]) {
    var priority = Heap<Node>()
    priority.insert(Node(vertex: start, cost: 0))
    visited[start] = 0
    while !priority.isEmpty {
        guard let curNode = priority.delete() else {
            break
        }
        if visited[curNode.vertex] < curNode.cost {
            continue
        }
        for node in graph[curNode.vertex] {
            if visited[node.vertex] > visited[curNode.vertex] + node.cost {
                visited[node.vertex] = visited[curNode.vertex] + node.cost
                priority.insert(Node(vertex: node.vertex, cost: visited[node.vertex]))
            }
        }
    }
}
var (sToV1, sToV2, v1ToV2, v1ToN, v2ToN) = (-1,-1,-1,-1,-1)
var startList = [0,v1,v2]
for i in 0..<startList.count {
    var visited = Array(repeating: Int.max, count: nodeCount)
    dijkstra(startList[i], visited: &visited)
    switch i {
    case 0:
        sToV1 = visited[v1]
        sToV2 = visited[v2]
    case 1:
        v1ToV2 = visited[v2]
        v1ToN = visited[nodeCount-1]
    case 2:
        v2ToN = visited[nodeCount-1]
    default:
        break
    }
}
var res = Int.max
if sToV1 == Int.max || v1ToV2 == Int.max || v2ToN == Int.max {
    res = Int.max
} else {
    res = min(res,sToV1+v1ToV2+v2ToN)
}
if sToV2 == Int.max || v1ToV2 == Int.max || v1ToN == Int.max {
    res = Int.max
} else {
    res = min(res,sToV2+v1ToV2+v1ToN)
}
print(res == Int.max ? -1 : res)