[알고리즘] 프로그래머스 - 합승 택시 요금

문제

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

프로그래머스

 

 

풀이

그냥 정한 문제인데 문제를 보니까 마침 우리가 요새 많이 풀고 있는 최단경로 문제라서 반가웠다.

백준에서 최단경로 문제를 푸는것도 좋지만 해당 알고리즘이 어떤식으로 코테에서 나오나...궁금했는데 활용 문제 느낌? 이어서 딱 좋은 타이밍에 푼 것 같다.

 

문제를 처음 봤을 때 함께 타고 가는 걸 어떻게 처리할지가 고민이었다. 왜냐면 함께 타는건 한번만 더해줘야 하고 각자 따로 타는건 따로 또 넣어줘야(?) 하는 것이기 때문에 그걸 어케 처리할까 생각하다가

 

최단경로 문제이기 때문에 결국 최단경로를 잘 구워삶아보자...생각했고 내가 생각한 풀이는

 

1. 합승했을 때를 고려해서 시작 지점에서 모든지점에 대한 최단 경로를 구한다.

2. 모든 지점에 대해 a에 대한 최단 경로를 구한다.

3. 모든 지점에 대해 b에 대한 최단 경로를 구한다.

 

그럼 결국 합승했을때 최단경로(시작 지점에서 해당 지점(k)까지의 최단경로) + 해당 지점(k)에서 a까지 가는 최단 경로 + 해당 지점(k)에서 b까지 가는 최단 경로가 가장 짧은게 최소 요금이 된다.

따라서 시작지점, a,b 이 3개에 대해 다익스트라를 수행하고 그 결과값으로 답을 구할 수 있었다. 효율성과 정확성에서 다 맞았으나 속도가 엄청 느렸다.

다시 보니까 내가 모든 지점에 대해 a에 대한 최단 경로를 구할 때,모든 지점을 시작지점으로 정하고 a에 대한 최단경로를 다시 least_cost에 넣어주는 식으로 했는데, 사실 그럴 필요가 없는 문제다. 왜냐면 양방향 도로여서  a->c로 가는 최단경로는 c->a로 가는 최단경로와 동일하기 때문에 그냥 a에 대해서 모든 지점에 대한 최단경로를 구하면 됐다. 그래서 다익스트라 부분을 수정해줬고 효율성이 엄청나게 개선됐다 :) 

 

코드

코드 개선 전

import heapq

def find_least(node,n,graph):
    least_cost = [1e9 for _ in range(n+1)]
    least_cost[node] = 0
    for i in range(1,n+1):
        if i == node:
            continue
        cost = [1e9 for _ in range(n+1)]
        cost[i] = 0
        q = []
        heapq.heappush(q,(0,i))
        
        while q:
            c , v = heapq.heappop(q)
            
            if cost[v] < c:
                continue
            for c_c,c_v in graph[v]:
                if cost[c_v] > c + c_c:
                    cost[c_v] = c + c_c
                    heapq.heappush(q,(c+c_c,c_v))
        least_cost[i] = cost[node]
        
    return least_cost
    
def solution(n, s, a, b, fares):
    answer = 1e9
    graph = [[]for _ in range(n+1)]
    
    for c,d,f in fares:
        graph[c].append((f,d))
        graph[d].append((f,c))
        
    # 모든 지점에 대해 a,b로 가는 최소 비용을 구한다. (따로 요금) 
    # 시작 지점에서 모든 지점에 대한 최소 비용 구하기 (합승 요금)
    # 모든 지점에 대해 최소 비용 구하기
    
    a_least_cost = find_least(a,n,graph)
    b_least_cost = find_least(b,n,graph)
    start_least_cost = find_least(s,n,graph)
    
    for i in range(1,n+1):
        answer = min(answer,start_least_cost[i]+a_least_cost[i]+b_least_cost[i])
    
    return answer

 

코드 개선 후

import heapq

def find_least(node,n,graph):
    cost = [1e9 for _ in range(n+1)]
    cost[node] = 0
    q = []
    heapq.heappush(q,(0,node))
    
    while q:
        c , v = heapq.heappop(q)
        
        if cost[v] < c:
            continue
        for c_c,c_v in graph[v]:
            if cost[c_v] > c + c_c:
                cost[c_v] = c + c_c
                heapq.heappush(q,(c+c_c,c_v))
        
    return cost
    
def solution(n, s, a, b, fares):
    answer = 1e9
    graph = [[]for _ in range(n+1)]
    
    for c,d,f in fares:
        graph[c].append((f,d))
        graph[d].append((f,c))
        
    # 모든 지점에 대해 a,b로 가는 최소 비용을 구한다.
    # 시작 지점에서 각 지점에 대한 최소 비용 구하기
    # 모든 지점을 거쳐 a,b로 가는게 더 비용이 적게 드는지 확인
    a_least_cost = find_least(a,n,graph)
    b_least_cost = find_least(b,n,graph)
    start_least_cost = find_least(s,n,graph)
    
    for i in range(1,n+1):
        answer = min(answer,start_least_cost[i]+a_least_cost[i]+b_least_cost[i])
    
    return answer