[Swift 알고리즘] 프로그래머스(Lv.3) - 합승 택시 요금 / 2021 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 합승 택시 요금" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 합승 택시 요금

 

---

풀이

이번 문제는 플로이드 와샬 문제입니다. (최적화한 다익스트라도 가능)

다익스트라는 최적화를 해도 언어에 따라 시간초과가 나는 경우가 있다고 해요.

 

제가 참고한 다익스트라와 플로이드 와샬의 차이점을 정리한 글 링크입니다.

정말 핵심만 비교해주셔서 한 번 봐보시면 좋을 것 같아요.

https://codedoc.tistory.com/95

플로이드, 다익스트라 알고리즘 비교

 

0. 합승의 개념 이해하기

합승이라는 것이 처음에는 생소했습니다.

합승이라는 것은 "어딘가를 거쳐 목적지로 이동한다."라고 생각하면 좋습니다.

A에서 C까지 가야 할 때 A -> C로 가는 것이 적게 드는지, A -> B -> C로 가는 것이 적게 드는지 비교하면 됩니다.

 

1. 그래프 생성하기

인접 행렬로 양방향 그래프를 생성합니다. 각 위치에 cost를 저장합니다.

 

2. 모든 정점에 대해 A에서 B로 가는 최소 비용을 구합니다.

A에서 B로 직접 가는 것과 C를 거쳐 가는 것 중 어느 것이 최소인지 비교합니다.

최소 비용을 graph[A][B]에 저장합니다.

아래 코드의 "to -> middle / middle -> from 구하기" 주석 아래 반복문입니다.

 

3. 각자 가는 것과 합승하는 것을 비교합니다.

각자 가는 것과 합승하는 것 중 어느 것이 최소 비용인지 비교합니다.

그 중 최소를 저장합니다.

 

후기

 

플로이드 와샬과 다익스트라의 차이점에 대해 더 잘 알게 된 기회였습니다.

 

감사합니다!

---

전체 코드

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    var result = 0
    
    var graph: [[Int]] = Array(repeating: Array(repeating: Int.max, count: n+1), count: n+1)
    
    //그래프 생성
    for fare in fares {
        graph[fare[0]][fare[1]] = fare[2]
        graph[fare[1]][fare[0]] = fare[2]
    }
    
    //to -> middle / middle -> from 구하기
    for middle in 1...n {
        for to in 1...n {
            guard graph[to][middle] < Int.max, to != middle else { continue }
            
            for from in 1...n {
                guard graph[middle][from] < Int.max, middle != from, to != from else { continue }
                
                //to -> from or to -> middle -> from
                graph[to][from] = min(graph[to][from], graph[to][middle] + graph[middle][from])
            }
        }
    }

    //직접 가는 것 vs 합승하는 것
    result = graph[s][a] + graph[s][b]
    for i in 1...n {
        let start = graph[s][i]
        let aCost = a == i ? 0 : graph[i][a]
        let bCost = b == i ? 0 : graph[i][b]
        
        guard start < Int.max, aCost < Int.max, bCost < Int.max else { continue }
        
        result = min(result, start + aCost + bCost)
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.