BOJ-1916 최소비용 구하기 Swift

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

내가 푼 풀이

 

접근방법: 다익스트라 알고리즘

1. 주어진 버스들로 2차원 배열을 만든다 (arr[i][j]: i도시에서 j도시까지의 거리)

1-1. 출발지와 도착지가 동일한경우 더 작은값을 넣는다.

2. 최단거리를 저장할 배열을 만든다.

3. 다익스트라 탐색을 이용해 이동가능한 버스를 통해 최단거리를 갱신한다.

4. 최종 갱신된 최단거리 배열에서 도착점의 원소 출력

 

import Foundation

// 입력받기
let N = Int(readLine()!)!
let M = Int(readLine()!)!
var cities = Array(repeating: Array(repeating: Int.max, count: N+1), count: N+1)
var bus = [[Int]]()
for i in 0..<M {
    let b = readLine()!.split(separator: " ").map{Int(String($0))!}
    bus.append(b)
}
let direct = readLine()!.split(separator: " ").map{Int(String($0))!}

// 2차원 배열로 만들기 cities[i][j] : i도시에서 j도시로 가는 거리
// 출발지와 목적지가 동일한 버스가 주어진다면 값비교해서 최솟값만 넣기
for i in bus {
    if cities[i[0]][i[1]] == Int.max {
        cities[i[0]][i[1]] = i[2]
    } else {
        if cities[i[0]][i[1]] > i[2] {
            cities[i[0]][i[1]] = i[2]
        }
    }
    
}
// 최단경로를 저장해놓을 배열
var md = Array(repeating: Int.max, count: N+1)
md[direct[0]] = 0
var queue = [(cur: direct[0], cost: 0)]

// 탐색
while !queue.isEmpty {
    let node = queue.removeFirst()
    for i in 1...N {
        // 현재 도시와 인접도시가 버스를 통해 갈 수 있고, 저장된 최단거리보다 더 짧다면 갱신해주고, 큐에 삽입
        if cities[node.cur][i] != Int.max && md[node.cur] + cities[node.cur][i] < md[i] {
            md[i] = md[node.cur] + cities[node.cur][i]
            queue.append((cur: i, cost: md[i]))
        }
    }
}
print(md[direct[1]])