[프로그래머스] 2021 Kakao Blind Recruitment - 합승 택시 요금

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

입력 & 출력

문제는 링크에서 확인바랍니다

풀이

S에서 시작해, A와 B를 공통으로 거쳐 각 지점까지 도착하는 최소값을 구해야한다
첫째로 생각난 방법은 A와 B를 가는 길을 모두 구하는 방법이다
S를 기준으로 A와 B를 가는 방법을 모두 구한 뒤, 두 배열에 공통적으로 들어가는 부분을 추려
겹치는 것이 가장 많은 것부터 차근히 요금을 구하는 방식이다

플로이드 와샬 기법으로 풀어보자
플로이드 와샬 기법은 3중 포문을 활용한, DP 작업이다

 for k in 0..<n {
    for i in 0..<n { // 출발 노드
        for j in 0..<n { // 도착 노드
            array[i][j] = min(array[i][k] + array[k][j], array[i][j])
        }
    }
}

노드 i ~ 노드 j 경로 값과, 노드 i ~ 노드 k 경로 + 노드 k ~ 노드j 경로 값을 비교해 더 적은 값을 저장한다
경로의 최소값을 구하는 것이니 더 큰 값은 사용하지 않는다
DP를 이용한 메모제이션이니 arr[][] 배열을 선언해 그 수를 초기화해야한다
위 과정에서 우리는 더 적은 값으로 저장하는 식을 가졌으니
arr 배열안에 들어가는 초기값은 경로가 가질 수 있는 가장 큰 수이다

최소 경로가 모든 경로를 지났을 경우, 최소 경로는 n * 경로의 값이 된다
경로(요금)가 가질 수 있는 가장 큰 값은 100,000으로 주어졌고, n은 200이하이니
배열의 초기값은 200 * 100,000이다

문제에서 제시한 예시를 보며 풀어보자

입출력 예제 1번

i번 노드가 j번 노드로 이어진 경우 = 경로 담기
i번 노드가 j번 노드로 이어지지 않는 경우, 노드가 자기 자신일 경우 = 패스
현재 배열은 최대값(max)로 초기화 되어있다

노드	1번	2번	3번	4번	5번	6번
1번	max	max	41	10	24	25
2번	max	max	22	66	max	max
3번	41	22	max	max	24	max
4번	10	66	max	max	max	50
5번	24	max	24	max	max	2
6번	25	max	max	50	2	max

과정을 반복하다보면 아래와 같은 배열이 만들어진다
A 노드에서 B 노드로 갈 수 있는 최소 경로값 배열이다

노드	1번	2번	3번	4번	5번	6번
1번	max	63	41	10	24	25
2번	63	max	22	66	46	48
3번	41	22	max	51	24	26
4번	10	66	51	max	34	35
5번	24	46	24	34	max	2
6번	25	48	26	35	2	max

A와 B 노드의 공통 경로가 없을 경우, 최소 경로는 ( S 노드 ~ A 노드 ) + ( S 노드 ~ B 노드 ) 경로 값이 된다
A와 B 노드의 공통 경로가 있을 경우, 현재 최소 경로와
(S 노드 ~ A,B 공통 노드) + (A,B 공통 노드 ~ A 노드) + (A,B 공통 노드 ~ B 노드) 중 더 적은 값이 된다

 

Swift 전체 코드

let max = 100000 * 200 // f * n 최대값
var array = Array(repeating: Array(repeating: max, count: n), count: n)
var minValue = max

for f in fares {
    let n1 = f[0] - 1
    let n2 = f[1] - 1
    array[n1][n2] = f[2]
    array[n2][n1] = f[2]
}

// 플로이드 와샬 방법
for k in 0..<n {
    for i in 0..<n {
        if array[i][k] == max || k == i {
            continue
        }
        for j in 0..<n {
            array[i][j] = i == j ? 0 : min(array[i][k] + array[k][j], array[i][j])
        }
    }
}

for i in 0..<n {
    minValue = min(minValue, array[s-1][i] + array[i][a-1] + array[i][b-1])
}

return minValue