특정 위치까지는 함께 이동하고 나머지는 따로 이동할 때 최단거리 구하기

 코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

 

A,B가 s에서 출발하는데 어떤 위치까지는 함께 갈 수 있고 그러다가 각자 도착 위치 a,b로 간다고 한다면...

 

최소 요금은 얼마인가

 

물론 함께가지 않아도 최소라면 그래도 된다

 

복잡하게 생각하면 상당히 어렵다..

 

어디까지 함께 가야하나?.. 함께 가는 거리가 최소여야하나??...

 

함께 가는 거리가 최소더라도.. 나머지 A,B까지 가는 거리는 최소로 해야하나???...

 

함께 가는 거리가 최소가 아니더라도.. 나머지 A,B까지 가는 거리가 최소일수도 있는거 아닌가..???

 

단순하게 생각하면..

 

s에서 어떤 지점 K까지 함께간다고 하자.

 

그리고 K에서 나머지 A,B까지 나눠서 간다고 하자.

 

그러면 dp[s][k] + dp[k][a] + dp[k][b]의 최솟값을 구하는 문제가 된다.

 

이를 모든 k = 1,2,3,...,n에 대해 조사해보면 된다. 

 

이런 알고리즘은 플로이드 워셜로 어떤 지점 i에서 모든 지점 j = 1,2,3,..,n까지 거리의 최솟값 dp를 구해놓는다.

 

그리고 모든 k = 1,2,3,..,n에 대해서 dp[s][k] + dp[k][a] + dp[k][b]가 최소가 되는 값을 찾는다.

 

 

#어떤 지점까지 함께 가고 나머지는 a,b로 나눠서 갈때 최소 거리를 구하는 방법
def solution(n, s, a, b, fares):
    
    INF = 1000000000000000000000000000000000000
    
    dp = [[INF]*(n+1) for _ in range(n+1)]
    
    for i in range(1,n+1):
        dp[i][i] = 0
    
    for p,q,f in fares:

        dp[p][q] = f
        dp[q][p] = f
    
    #플로이드 워셜로 어떤 지점 i에서 모든 지점 j = 1,2,..,n까지 최소 거리를 찾는다
    for k in range(1,n+1):
        
        for i in range(1,n+1):
            
            for j in range(1,n+1):
                
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
    
    #s에서 k까지 함께 간다고 하고, k에서 a, k에서 b로 나눠서 간다고 하자.
    #그러면 dp[s][k] + dp[k][a] + dp[k][b]의 최솟값을 구하는 문제가 된다.
    answer = INF
    
    for k in range(1,n+1):
        
        if answer > dp[s][k] + dp[k][a] + dp[k][b]:
            
            answer = dp[s][k] + dp[k][a] + dp[k][b]
            
    return answer