[프로그래머스][KAKAO_BLIND][2021] 합승 택시 요금

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

# 시간초과 (80점)
from collections import defaultdict
import heapq, sys

def make_graph(fares):
    graph = defaultdict(list)
    for _from, _to, fare in fares:
        graph[_from].append((fare, _to))
        graph[_to].append((fare, _from))
    return graph

def dijkstra(graph, memo, n, s, e):
    if memo[s][0] != -1:
        return memo[s][e]

    q = [(0, s)]
    weights = [sys.maxsize] * (n+1)
    visited = [False] * (n+1)

    while q:
        w, d = heapq.heappop(q)
        visited[d] = True

        if w < weights[d]:
            weights[d] = w

        for nw_w, nw_d in graph[d]:
            if not visited[nw_d]:
                heapq.heappush(q, (w+nw_w, nw_d))

    memo[s] = weights
    return weights[e]

def solution(n, s, a, b, fares):
    answer = sys.maxsize
    graph = make_graph(fares)
    memo = [[-1] for _ in range(n+1)]
    for i in range(1, n + 1):
        answer = min(answer, dijkstra(graph, memo, n, s, i) + dijkstra(graph, memo, n, i, a) + dijkstra(graph, memo, n, i, b))
    return answer

• 다익스트라를 이용한 최소 가중치 구하기
  
  • (시작-중간) + (중간-a) + (중간-b)에 대해 다익스트라 적용
• 시간초과로 DP 적용
  • 그래도 시간초과

 

다른 사람이 작성한 코드

from heapq import heappop, heappush

INF = int(1e9)
graph = [[]]

def preprocess(n, fares):
    global graph
    graph = [[] for i in range(n+1)]

    for fare in fares:
        src, dst, cost = fare[0], fare[1], fare[2]
        graph[src].append([dst, cost])
        graph[dst].append([src, cost])

def dijkstra(src, dst):
    global graph
    n = len(graph)
    table = [INF for i in range(n)]
    table[src] = 0
    pq = [[0, src]]

    while pq:
        w, x = heappop(pq)

        if table[x] < w: continue

        for item in graph[x]:
            nx, ncost = item[0], item[1]
            ncost += w
            if ncost < table[nx]:
                table[nx] = ncost
                heappush(pq, [ncost, nx])
    
    return table[dst]

def solution(n, s, a, b, fares):
    preprocess(n, fares)
    cost = INF

    for i in range(1, n+1):
        cost = min(cost, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b))
    
    return cost

• 같은 방식인데 DP가 없어도 시간초과가 나지 않음

https://velog.io/@study-dev347/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%95%A9%EC%8A%B9-%ED%83%9D%EC%8B%9C-%EC%9A%94%EA%B8%88

[프로그래머스] 합승 택시 요금(Python)

 

기억해야할 것

• 다익스트라 작성 방식을 변경해야할듯
  
  • 큰 그림에서 비슷하지만, 다익스트라 방식에 따라 시간초과 차이가 생김
  • 위에 작성하신 분의 방식을 숙지해서 다익스트라 구현을 숙지해야겠다
• 두 다익스트라의 차이는 queue의 append 조건으로 인한 size 차이
  • 현재 weight가 저장된 weight보다 크면 continue
    - 나는 탐색할 필요가 없음에도 visited가 아닌 노드에 대한 edge는 추가했음
    - 그러나 이 조건만 추가하면 여전히 시간초과 (개선은 됨)
  • 새로 탐색한 edge의 가중치 합이 저장된 wieght보다 크면 continue
    - 나는 visitied가 아니면 일단 추가
    - 이로 인해 queue에 push되는 조건이 까다로워져, 탐색할 양이 줄어듦
  • 주의사항
    - 인접 노드에 대한 weight값만 업데이트하므로, 시작 weight를 0으로 초기화해줘야함