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

[프로그래머스][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

기억해야할 것

다익스트라 작성 방식을 변경해야할듯

큰 그림에서 비슷하지만, 다익스트라 방식에 따라 시간초과 차이가 생김 위에 작성하신 분의 방식을 숙지해서 다익스트라 구현을 숙지해야겠다

두 다익스트라의 차이는 queue의 append 조건으로 인한 size 차이 현재 weight가 저장된 weight보다 크면 continue

- 나는 탐색할 필요가 없음에도 visited가 아닌 노드에 대한 edge는 추가했음

- 그러나 이 조건만 추가하면 여전히 시간초과 (개선은 됨) 새로 탐색한 edge의 가중치 합이 저장된 wieght보다 크면 continue

- 나는 visitied가 아니면 일단 추가

- 이로 인해 queue에 push되는 조건이 까다로워져, 탐색할 양이 줄어듦 주의사항

- 인접 노드에 대한 weight값만 업데이트하므로, 시작 weight를 0으로 초기화해줘야함

from http://pythaac.tistory.com/199 by ccl(A) rewrite - 2021-08-25 14:26:55