[Swift] BOJ 1238 파티

BOJ 1238 파티

 

접근 방식

 

각 마을이 파티가 열리는 마을 X로 갔다가 돌아오는 데 걸리는 최대 시간을 구하는 문제. 갈 때는 마을마다 다익스트라를 돌려 X까지의 거리를 구하고, 올 때는 X에서 다익스트라를 한 번 돌려 모든 마을까지의 거리를 구한 뒤 두 값을 더해 최댓값을 취함.

 

단방향 도로라 갈 때와 올 때 거리가 다르므로, 각 마을에서 X로 가는 최단 거리는 마을 수만큼 따로 구해야 함. 반면 돌아오는 길은 모두 X에서 출발하므로 한 번이면 충분함.

 

효율을 높이려면 우선순위 큐(힙)를 직접 구현해야 하는데, Swift에는 기본 제공이 없어 손이 많이 감.

 

코드

 

//
//  b1238.swift
//  Algorithm
//
//  Created by Hamlit Jason on 2022/05/11.
//
// https://www.acmicpc.net/problem/1238
import Foundation

struct b1238 {
    static func run() {
        let input = readLine()!.split(separator: " ")
        var graph = [String: [String: Int]]()
        
        for _ in 0..<Int(input[1])! {
            let item = readLine()!.components(separatedBy:" ")
            let start = String(item[0])
            let end = String(item[1])
            let cost = Int(item[2])!
            
            if graph[item[0]] == nil {
                graph[start] = [end: cost]
            } else {
                var a = graph[start]!
                a[end] = cost
                graph[start] = a
            }
        }
        
//        print(graph)
        
        var timeList = [Int](repeating: 0, count: Int(input[0])! + 1)
        
        // 갈때
        for n in 1...Int(input[0])! {
            let answer = dijkstra(graph: graph, start: String(n))
            timeList[n] = answer[String(input[2])]!
        }
        
//        print(timeList)
        
        // 돌아올 때
        let answer = dijkstra(graph: graph, start: String(input[2]))
        answer.forEach {
            timeList[Int($0)!] += $1
        }
//        print(timeList)
        print(timeList.max()!)
        
        
    }
}