[프로그래머스] Swift - 합승 택시 요금

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

 

2023.07.23 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

합승을 해서 특정 노드까지는 같이가고 해당 지점에서 두 사람이 헤어져서 각자의 도착지로 이동해야 하는 문제입니다.

앞서 특정 노드까지는 같이 간다는 점이 중요했습니다!

그 지점을 K 노드라고 한다면

1. S부터 K까지의 최단거리
2. K부터 A까지의 최단거리
3. K부터 B까지의 최단거리

이렇게 1~3번에서 구한 거리들을 더한 값이 정답이 되게 됩니다.

 

여기서 K가 S와 같은 값이라면 출발지에서 바로 두 사람이 헤어져서 이동하는 상황입니다.

K가 A 또는 B라면 한 사람의 목적지까지 같이 가고 다른 한사람은 계속 이어서 남은 거리를 이동하는 상황입니다.

즉, 이런 엣지 케이스들도 앞선 1~3번 과정을 계산하면 자동으로 포함되기 때문에 따로 계산할 필요가 없습니다!!

 

정리해보면 결국 각 노드끼리의 최단 경로를 구하는 최단 경로 알고리즘 문제입니다..!

 

이러한 최단 경로 문제를 푸는 방법에는 크게 2가지의 알고리즘 풀이법이 있습니다.

1. Floyd Warshall (플루이드-워셜)
2. Dijkstra (다이크스트라)

 

이번에는 둘 중에서 더 간단한 풀입버인 플루이드-워셜 알고리즘을 사용해서 풀어보았습니다. 

시간 복잡도 측면에서는 다이크스트라가 더 우위에 있습니다!! 

플루이드-워셜은 O(N^3)이고 다이크스트라는 구현 방법에 따라 O(N^2) 또는 O(N*LogN)입니다.

 

 

Floyd Warshall

플루이드-워셜의 개념은 간단합니다.

A에서 B까지의 최단 경로를 구하기 위해 중간 경로인 K를 사용합니다.

 

3중 반복문을 이용합니다.

K가 1번 노드부터 N번 노드까지인 경우를 전부 조사합니다.

A부터 K까지의 거리를 AK, K부터 B까지의 거리를 KB라고 한다면,

결과적으로 A부터 B까지의 거리는 AK+KB입니다.

 

A와 B또한 반복문으로 1씩 증가시키면서 AK+KB 값을 이전에 구한 값들과 비교하여 더 작은 값을 저장합니다.

이 부분은 DP와 같습니다.

for k in 1..<n+1 {
    for a in 1..<n+1 {
        for b in 1..<n+1 {
            distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])
        }
    }
}

 

풀이

fileprivate func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    // Floyd-Warshall (플로이드 워셜 알고리즘)
    var distance = Array(repeating: Array(repeating: 1_000_000, count: n+1), count: n+1)
    
    for i in 1..<n+1 {
        distance[i][i] = 0
    }
    
    for fare in fares {
        let departure = fare[0]
        let arrival = fare[1]
        distance[departure][arrival] = fare[2]
        distance[arrival][departure] = fare[2]
    }
    
    for k in 1..<n+1 {
        for i in 1..<n+1 {
            for j in 1..<n+1 {
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
            }
        }
    }
    
    var result = Int.max
    
    for k in 1..<n+1 {
        result = min(result, distance[s][k]+distance[k][a]+distance[k][b])
    }
    
    return result
}

2차원 배열인 distance에 각 노드까지의 최단 거리를 기록합니다.

 

distance의 초기값을 처음에 100,000으로 주었는데 이렇게 하면 마지막 테스트 케이스에서 실패가 나왔습니다.

문제에서 각 요금의 최댓값이 100,000이라고 해서 그렇게 넣은 것이었는데 사실 생각해보면 A 노드에서 B노드까지 바로 가는 간선이 없고 여러 노드를 들려서 가야한다면 100,000이 여러번 더해져야 할 수 있기 때문에 당연하게도 디폴트 값을 더 크게 설정하는 것이 맞았습니다.

따라서 디폴트 초기값을 1,000,000으로 주었고 테스트 케이스를 통과했습니다.

마무리

최단 경로 문제였고 플로이드 워셜 알고리즘을 사용하여 해결했습니다.

 

시간 복잡도가 O(N^3)이기에 실행 시간이 오래 걸릴 수 있지만 문제 조건에서 n이 200 이하라고 했기 때문에 높은 시간 복잡도에도 불구하고 테스트 케이스를 통과할 수 있었습니다.

 

다음번 최단 경로 문제에서는 다이크스트라를 사용하여 풀어보겠습니다!