2021 카카오 공채 - 합승 택시 요금

 

 

[문제]
지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

 

해설

무지와 어피치가 시작지점(S)로 부터 각각의 집(A, B)에 도착할 수 있는 최소 금액을 찾는 문제

여기서 아예 1)합승을 하지 않을수도, 2)중간부터 따로 갈 수도, 3)아예 한 집에 들렸다 갈 수도 있다.

 

이와 같은 상황을 고려했을 때,

한 지점에서 다른 지점까지의 최단 거리를 구하는 다익스트라 알고리즘은 이용하기 어렵다.

 

그 대신 모든 지점 간의 최소 거리(금액)을 구하는

플로이드 워셜 알고리즘을 사용해서 먼저 각 지점간 최소 금액을 구해야한다.

--> 여기까지 했다면 거의 85% 해결

 

그 이후에는 어디까지 같이 갈 것인지만 확인하면 된다.

위에서 언급한 세 가지 루트에 대해 각각 설명하기 위해

시작 시점을 S, 따로 가기 시작한 지점을 I, 각각의 집을 A, B로 칭한다면

 

1) 합승을 하지 않은 경우는 I가 S가 되어

S->S + S->A + S->B

 

2) 중간까지 가다 헤어진 경우는

S->I + I->A + I->B

 

3) 한 집에 같이 가는 경우는(A에 먼저 간다고 가정) I가 A가 되어

S->A + A->A + A->B

 

즉 이 모든 경우는

S->I + I->A + I->B로 나타낼 수 있으며

1번부터 n번 지점까지 순회하며 최소 금액을 찾으면 정답을 구할 수 있다.

 

소스 코드 

from collections import deque

def solution(n, s, a, b, fares):
    answer = 0
    INF = 1000001
    fl = [[INF for _ in range(n)] for _ in range(n)]
    
    for c, d, f in fares:
        fl[c-1][d-1] = f
        fl[d-1][c-1] = f
        
    for i in range(n):
        fl[i][i] = 0
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k or i == j or k == j:
                    continue
                    
                tmp = fl[i][k] + fl[k][j]
                
                if tmp < fl[i][j]:
                    fl[i][j] = tmp
                    
    answer = -1
    
    for i in range(n):
        tmp = fl[s-1][i] + fl[i][a-1] + fl[i][b-1]
        if answer == -1 or tmp < answer:
            answer = tmp
    
    
    return answer

 

+ 몇몇 케이스가 실패하는 경우 INF 크기를 크게 만들어주면된다.

해당 문제에선 100001으로 딱 맞게 한 경우 실패함