Programmers - 합승 택시 요금 [Swift] #Floyd-Warshall

문제 링크

이 문제를 풀기 위해서는 모든 노드 간 최단 경로를 구하는 Floyd-Warshall 알고리즘을 활용해야 한다.

처음에 문제를 접근할 때, 합승하면 요금이 반틈으로 줄어드는 것도 고려를 해야한다고 생각했는데 아니였다..!

💡 알고리즘

1. 모든 노든 간 최단 경로를 구한다. (Floyd-Warshall 이용)
2. result 를 합승하지 않은 경우의 요금으로 초기설정한다.
3. 노드(i)를 차례대로 돌면서
   (출발시점 s → i) + (i 에서 a) + (i 에서 b)와 answer 중 더 작은 값을 answer로 업데이트한다.

Floyd-Warshall 알고리즘

https://chanhuiseok.github.io/posts/algo-50/

코드

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    var answer = 0
    var node: [[Int]] = []
	
    // 자기 자신은 0, 나머지는 무한으로 초기화
    for i in 0..<n{
        node.append(Array(repeating: 999999, count: n))
        node[i][i] = 0
    }
    
    // fares에 있는 비용으로 초기화
    for i in fares{
        node[i[0]-1][i[1]-1] = i[2]
        node[i[1]-1][i[0]-1] = i[2]
    }

    // Floyd-Warshal 알고리즘
    for k in 0..<n{ // 거쳐가는 node
        for i in 0..<n{
            for j in 0..<n{
                // i->j로 가는 비용과 i -> k -> j 즉, k를 거쳐가는 비용을 비교
                node[i][j] = min(node[i][j] , node[i][k] + node[k][j])
            }
        }
    }
    answer = node[s-1][a-1] + node[s-1][b-1]
    
    for i in 0..<n{
    	// s에서 i + i에서 a + i에서 b의 최소 비용을 구해준다.
        answer = min(answer, node[s-1][i] + node[i][a-1] + node [i][b-1])
    }
    
    return answer
}

참고 링크

https://velog.io/@sainkr/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%95%A9%EC%8A%B9-%ED%83%9D%EC%8B%9C-%EC%9A%94%EA%B8%88-Swift