[알고리즘/Swift] 1916 최소비용 구하기

문제 정보

문제 출처: 백준 온라인 저지
문제 링크: 1916 최소비용 구하기
제출 언어: Swift
알고리즘 분류:
- 그래프 이론
- 데이크스트라

풀이

DIJKSTRA

Negative Cycle이 없는 directed graph에서만 사용 가능하다
시작 node에서 다른 node로 가는 가장 짧은 경로를 구하여 최종적으로 시작 node에서 끝 node까지의 최종 최단경로를 구한다
이 문제에서는 다양한 버스 노선 중 주어진 도시 1에서 5로 가능 최단 경로를 찾는 알고리즘을 작성해야한다
다익스트라 알고리즘 작동 원리는 다음과 같다
- 1. 각 node까지의 경로 길이를 무한대로 초기화
- 1. 시작 node의 경로 길이를 0으로 초기화
- 1. 아직 포함되지 않은 node 중 최소인 것 선택하여 최단경로에 추가
- 1. 최단경로에 새로 추가된 node의 인접 node들에 대해 경로 길이를 갱신
- 1. 만약 graph내의 모든 node가 최단경로에 소속할 때까지 위의 과정 반복

학부 수업에서 배울 때에는 3 단계에서 새로운 최단 경로 집합을 생성하여 거기에 방문한 node를 넣어주어서 방문한 노드를 체크했는데,
해당 문제에서는 최단 경로보다는 도착 node까지의 비용만 알면 되므로 따로 새로운 집합에 node들을 추가해줄 필요가 없이 visited 배열 변수를 두고 방문 여부만 파악하였다

나만의 알고리즘

다음은 해당 문제에 적용한 알고리즘이다
1) 각 도시의 모든 경로의 비용을 무한대로 초기화
2) 시작 node의 경로의 비용를 0으로 초기화
3) 아직 방문하지 않은 node중에서 가장 길이가 짧은 node를 방문한다
4) 방문한 node의 인접한 node의 길이들을 업데이트 해준다 (방문한 node 비용+ 인접node로 가는 비용과 인접 node의 누적 비용 중 작은 값으로)
5) 끝 node에 방문할 때까지 3~5 작업을 반복한다

이해가 쉽지 않으니 그림이랑 설명하겠다
다음과 사진들과 같이 도시와 버스 노선을 그려보고, 출발지점, (도착지점, 비용)을 배열로 받아주었다
처음 입력을 받을 때 Dictionary형으로 받았었는데 Dictionary는 하나의 Key에 하나의 Value만 가질 수 있어서 부적절하였다
그래서 다중 배열로 출발지점과 도착지점, 비용 튜플을 받았다

for i in 0..<M{
    let n = readLine()!.split(separator: " ").map{Int(String($0))!}
    bus[n[0]].append((n[1], n[2]))
}
//출력 :
0 []
1 [(2, 2), (3, 3), (4, 1), (5, 10)]
2 [(4, 2)]
3 [(4, 1), (5, 1)]
4 [(5, 3)]
5 []

그 후 시작 node를 받은 후 현재 방문중인 도시가 도착점이 될 때까지 3~5를 반복한다

1) 각 도시의 모든 경로의 비용을 무한대로 초기화 2) 시작 node(도시 1)의 경로의 비용를 0으로 초기화

3) 아직 방문하지 않은 node중에서 가장 길이가 짧은 node(도시 1)를 방문한다

이 후 4) 인접한 node들의 길이를 업데이트 해준다

이 후 3) 아직 방문하지 않은 node중에서 가장 짧은 node(도시 4)에 방문한다

반복 4) 인접한 node들의 길이를 업데이트 해준다

이 후 3) 아직 방문하지 않은 node중에서 가장 짧은 node(도시 2)에 방문한다

반복 4) 업데이트 해줄 node가 없으니 넘어간다

이 후 3) 아직 방문하지 않은 node중에서 가장 짧은 node(도시 3)에 방문한다

반복 4) 업데이트 해줄 node가 없으니 넘어간다

이 후 3) 아직 방문하지 않은 node중에서 가장 짧은 node(도시 5)에 방문한다

5) 끝 node에 도달했으므로 최단 비용은 계산한 후 알고리즘을 종료한다

전체 코드

import Foundation

let N = Int(readLine()!)!
let M = Int(readLine()!)!
var bus: [[(Int, Int)]] = Array(repeating: [], count: N+1)
for i in 0..<M{
    let n = readLine()!.split(separator: " ").map{Int(String($0))!}
    bus[n[0]].append((n[1], n[2]))
}
let s = readLine()!.split(separator: " ").map{Int(String($0))!}
var (current, end) = (s[0], s[1])
var visited: [Bool] = Array(repeating: false, count: N+1)
var min_pay = [Int](repeating: Int.max, count: N+1)
min_pay[current] = 0
while visited[end] == false{
    var current = min_pay.enumerated().filter({!visited[$0.offset]}).min(by: {$0.element < $1.element})!.offset
    visited[current] = true
    for adj in bus[current]{
        if !visited[adj.0]{
            min_pay[adj.0] = min(min_pay[current] + adj.1, min_pay[adj.0])
        }
    }
}
print(min_pay[end])