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

 

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

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

 

그래프 문제

다익스트라와 플로이드-와샬 두 방법으로 풀 수 있다.

대부분 테스트 케이스에서 다익스트라가 더 빠르다.

 

두 알고리즘 모두 기본 원리는 이렇다.

A -> B 의 최단 거리(혹은 경로)를 탐색하기 위해 '중간점'을 끼워넣어보는 것이다.

예를 들어, A -> B 와 A -> C -> B 중 뭐가 더 짧을까? 혹은 A -> D -> B가 더 짧을까? 라는 식으로 말이다.

그래서 만약 A에서 B로 직접 가는 것보다 더 짧은 경로가 있다면, 그 거리로 원래의 거리를 갱신해주는 것이다.

간선이 없는 노드에 대해서는 거리를 무한대로 초기화 해둔다.

 

다익스트라 : 한 노드(출발점)으로부터 다른 노드까지의 최단 거리를 찾는 알고리즘 -> 알고리즘 결과 : 1차원 거리행렬

플로이드-와샬 : 모든 노드로부터 다른 노드까지의 최단 거리를 찾는 알고리즘 -> 알고리즘 결과 : 2차원 거리행렬

 

따라서 다익스트라를 모든 노드에 대해 수행하면 플로이드-와샬과 같은 결과를 얻는다.

이때, 다익스트라를 우선순위큐나 힙을 이용해 구현하면 수행 시간을 NlogN으로 줄일 수 있어서, 전체 수행 시간에서 조금 차이가 나는 것이다.

 

처음 그래프를 초기화 할 때는 인접리스트나 거리행렬을 사용하면 된다.

개인적으로 거리행렬이 더 편해서 거리행렬을 사용했다.

 

다익스트라 코드

# 다익스트라
from math import inf
from heapq import heappush, heappop


def dijkstra(n, graph, start):
    dist = [inf for _ in range(n)]  # start 기준의 거리행렬
    dist[start] = 0                 # 자기 자신으로 가는 간선은 0

    q = []
    heappush(q, [dist[start], start])           # 거리와 노드를 함께 큐에 삽입
    while q:                                    # (비용이 작은 노드를 먼저 선택)
        cur_dist, cur_dest = heappop(q)
        if dist[cur_dest] >= cur_dist:          # start에서 cur_dest로 가는 거리가
            for i in range(n):                  # 이미 저장된 거리보다 작을 때만 진행
                new_dist = cur_dist + graph[cur_dest][i]
                if new_dist < dist[i]:          # cur_dest를 거쳐 i로 가는 거리가
                    dist[i] = new_dist          # 이미 저장된 거리보다 작으면 갱신
                    heappush(q, [new_dist, i])  # 다음 인접한 노드를 고려하기 위해 큐에 삽입
    return dist


def solution(n, s, a, b, fares):
    s, a, b = s - 1, a - 1, b - 1   # 0부터 시작하는 인덱스
    graph = [[inf] * n for _ in range(n)]
    for fare in fares:
        u, v, w = fare
        graph[u - 1][v - 1] = graph[v - 1][u - 1] = w

    # 다익스트라
    # 모든 노드에 대해 다익스트라를 수행하고,
    # 반환된 1차원 거리행렬을 append 해줌
    min_graph = []
    for i in range(n):
        min_graph.append(dijkstra(n, graph, i))

    # 출발점을 기준으로 어떤 지점 k를 거쳐 각각 a와 b로 가는 최소 비용을 탐색
    ans = inf
    for k in range(n):
        ans = min(ans, min_graph[s][k] + min_graph[k][a] + min_graph[k][b])

    return ans

 

플로이드-와샬 코드

# 플로이드-와샬
from math import inf


def solution(n, s, a, b, fares):
    # 0부터 시작하는 인덱스
    s, a, b = s - 1, a - 1, b - 1

    # inf 로 초기화된 거리행렬
    # 자기 자신으로 가는 간선 가중치는 0
    graph = [[inf] * n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0     

    # 거리행렬에 주어진 비용 넣기
    for fare in fares:
        u, v, w = fare
        graph[u - 1][v - 1] = graph[v - 1][u - 1] = w

    # 플로이드-와샬
    for k in range(n):          # 1. 모든 노드를 중간점(경로)으로 가정하면서
        for i in range(n):      # 2. 거리행렬을 순회
            for j in range(n):  # 3. 현재 거리행렬에 저장된 거리가 k를 거쳐가는 거리보다 멀면 갱신
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                # graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) 시간 거의 두 배 걸림..

    # 출발점을 기준으로 어떤 지점 k를 거쳐 각각 a와 b로 가는 최소 비용을 탐색
    ans = inf
    for k in range(n):
        ans = min(ans, graph[s][k] + graph[k][a] + graph[k][b])

    return ans

 

처음에 플로이드-와샬로 풀었을 때, 저 주석 처리된 부분 때문에(min 하는 부분) 효율성 26번에서만 시간 초과가 났다!!! 조건문으로 고치고 나니까 시간이 거의 반절 줄었다,, 헊쓰