합승 택시 요금

Wonbin Kim·2022년 12월 26일
0

알고리즘

목록 보기
4/5

문제 출처 및 풀이 코드

2021 KAKAO BLIND RECRUITMENT

깃헙 코드

문제 요약

  • 주어진 그래프는 무방향 그래프
  • 출발 지점(s)에서 택시를 합승하고, 그리고나서 중계점(k)에서 각각 택시를 타고 헤어져서 각각의 도착 지점(a,b)으로 갈 때의 최저 택시 요금 구하기
  • 최초에 택시는 합승을 할 수도, 안할 수도 있음
  • 경우에 따라 중계점이 a 또는 b 지점이 될 수도 있음

문제 풀이

  • 문제의 핵심 풀이는 택시를 합승해서 내리는 위치를 k라고 할 때, 택시 요금은 아래와 같이 정의할 수 있다.

    f(s,a,b,k) = fare(s, k) + fare(k, a) + fare(k, b)

  • 이 때 k는 합승을 마치고 각자 택시를 타는 지점이고, fare(v,w)는 정점 v와 w의 최저 택시 요금이다.

  • 함수 f를 최소로 만드는 값은, 다른 값은 고정이므로 f를 최소로 만드는 k값을 찾는것이다.

  • 각 fare의 항목에 들어가는 함수 값은 k에 따라 값이 변화하므로 모든 가능한 k 값에 대한 fare 항목들의 최솟값을 구해야한다

  • 따라서 각 지점으로부터 각 지점으로까지의 최소 거리를 구하는 알고리즘인 floyd-warshall algorithm을 사용하였다.

코드

def solution(n, s, a, b, fares):
          
    # 최댓값에 대한 가정, 요금 f의 범위가 [1, 100,000]이고,
    # 징점의 개수는 최대 200이기 때문에 가능한 최댓값은 19,900,000이지만 넉넉하게 잡았다. 
    INF = 100000000
    
    # make adjacency matrix   
    distance = [[INF for _ in range(n)] for _ in range(n)]
    # initialize weights for line to itself
    for i in range(n):
        distance[i][i] = 0
    
    for i, j, weight in fares:
        distance[i-1][j-1] = weight
        distance[j-1][i-1] = weight # 양방향 그래프이므로 반대 방향으로도 간선을 놓는다.
        
    #floyd-warshall algorithm
    def floyd_warshall(G):
        
        for k in range(n): # 중간노드 k에 대해서
            for i in range(n): # 시작노드 i에 대해서
                for j in range(n): # 끝노드 j에 대해서
                    G[i][j] = min(G[i][j], G[i][k]+G[k][j])
    
    floyd_warshall(distance) # 요금에 대한 인접 행렬을 가지고 floyd-warshall 알고리즘

	# 그리고 중계점 k에 대해 가능한 모든 경우에서 가장 작은 값을 구한다.
    answer = min([distance[s-1][k]+distance[k][a-1]+distance[k][b-1] for k in range(n)])
        
    return answer

이 번에 새로 배운 것

  • floyd-warshall algorithm refresh
profile
열심히 노력해야하는 사람

0개의 댓글