[백준/Swift] 11779: 최소비용 구하기 PS일지

문제

11779번: 최소비용 구하기 2

간단한 문제 요약

  다익스트라 최단 경로 문제입니다! A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시켜야합니다. 이때 A->B까지 갈 때 최소로 드는 비용과 경로를 출력해야한다. 출 -> 도착 지점은 항상 지정되어있다.

 

고려해야 할 사항

• 문제를 구현하면서 답은 여러 개가 정답일 수 있습니다.

문제 풀이, 했갈렸던 점  PS 일지

 문제를 풀면서 신기했던 점이 있습니다. 예제 입력에 대한 예제 출력의 도시 경로 출력의 경우가 여러 개가 답이 나올  수 있다는 점입니다. 예제 입력에 대한 input을 바탕으로 직접 그린 결과 1->4->5 or 1->3->5 두 가지의 경로가 존재했습니다.(예제 출력에 없어도 답이 맞을 수 있는게 당연한건데 그래도 멈칫했네요..)

 

 요즘 다익스트라 알고리즘을 계속 공부하고 있는데요 매번 문제가 새롭다는 것을 느낍니다. 

 

 이번 문제는 최단 경로 탐색과 최단 경로 탐색시에 방문한 도시를 기록해서 출력하는 문제 입니다. Node에는 vertex, cost 를 변수로 갖는 구조체를 선언 했습니다. 처음엔 Node에 배열을 변수로 추가해서 방문 했을 때의 기록을 남길까 생각 했었는데 메모리를 너무 많이 사용할 것 같다는 생각이 들었습니다.

 다익스트라 최단 경로 탐색을 할 때 새로 탐색할 node의 최단 비용(visited[node.vertex])보다 현재 정점에서 지금 위치한 출발정점에서 도착할 정점 node의 node.cost 만큼의 비용이 더 최단이라면 어차피 최단 cost를 새로 갱신하는데 이를 이용했습니다.

 

//visited정점은 최단 비용을 저장하는 배열

//seq는 최단 경로를 거쳐 갈 때 노드를 저장합니다.

 

예를들어 seq[B] = a 라는 뜻은 B 정점은 A를 통해 최소한의 비용으로 방문이 가능하다는 뜻입니다.

sec[C] = B 인 것은 C 정점까지 도착하기 위해선 B 정점을 거쳐야합니다.

근데 sec[B] = A 인 것으로 보아

C 정점은 B 정점을 거치고, B정점은 정점을 거쳐야 한다는 결론을 얻을 수 있습니다.

D입장에서 보면 원래 B였다가 C로 갱신됩니다. 그 이유는 visited[D] 에는 200이 저장 되어 있다고 가정했을 때 visited[C](110) + 10 을 한 결과가 더 최소 비용임으로 visited[D] = visited[C] + C.cost를통해 visited[D]의 최단 비용을 갱신하고 seq[D] = C를 저장합니다.

 seq[D] = C. seq[C] = B. seq[B] = A

역으로 추적을 하면

A -> B -> C -> D입니다. A->D까지 최단 경로 탐색시에 방문한 정점의 순서를 알 수 있다는 점입니다.

코드

로직

struct Node {
    var vertex: Int
    var 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
    }
}
var nCnt = Int(readLine()!)!
var graph = Array(repeating: [Node](), count: nCnt)
(0..<Int(readLine()!)!).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))
}
var se = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (start, end) = (se[0]-1,se[1]-1)
var seq = Array(repeating: 0, count: nCnt)
var visited = Array(repeating:Int.max, count: nCnt)

func dijkstra() {
    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
                seq[node.vertex] = curNode.vertex
                priority.insert(Node(vertex: node.vertex, cost: visited[node.vertex]))
            }
        }
    }
}

dijkstra()
var res = ""
res += "\(visited[end])\n"
var ans = [Int]()
ans.append(end+1)
var vertex = end
while vertex != start {
    vertex = seq[vertex]
    ans.insert(vertex+1, at: 0)
}
res += "\(ans.count)\n"
res += ans.reduce(""){"\($0)\($1) "}
print(res)

힙

struct Heap<T> where T: Comparable {
    private var list = [T]()
    var isLeftSmall: (T,T) -> Bool
    init(isLeftSmall: @escaping (T,T)->Bool) {
        self.isLeftSmall = isLeftSmall
    }
    init() {
        self.init(isLeftSmall: <)
    }
}

extension Heap {
    var isEmpty: Bool {
        return list.isEmpty
    }
    var peek: T? {
        return list.first
    }
    var count: Int {
        return list.count
    }
}
extension Heap {
    mutating func insert(_ element: T) {
        var idx = 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() }
        let element = list.first!
        var idx = 0
        list.swapAt(idx, count-1)
        _ = list.removeLast()
        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
    }
}