합승 택시 요금

날짜 : 2023. 10. 09

사용 언어 : python

 

문제

 

코드

다익스트라

import heapq
INF = int(1e9)
def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n + 1)]
    for edge in fares:  # 각 노드와 연결된 edge 체크
        p, q, cost = edge
        graph[p].append([q, cost])
        graph[q].append([p, cost])
        
    def dijkstra(start, end):
        dist = [INF] * (n + 1)
        dist[start] = 0  # 현재노드
        queue = list()
        heapq.heappush(queue, [0, start])
        while queue:
            d, now = heapq.heappop(queue)  # 저장된 노드 체크
            if dist[now] < d: # 기존 start ~ now 거리와 비교
                continue  
            for edge in graph[now]:  # now와 연결된 edge 체크
                cost = d + edge[1] 
                if cost < dist[edge[0]]:
                    dist[edge[0]] = cost
                    heapq.heappush(queue, [cost, edge[0]])  # 다음에 이동할 노드, 그 노드까지의 거리 저장
        return dist[end]  # start에서 도착지까지의 최소값
    
    res = dijkstra(s, a) + dijkstra(s, b)
    for via in range(1, n + 1):
        if via == s: continue
        res = min(res, dijkstra(s, via) + dijkstra(via, a) + dijkstra(via, b))
    
    return res

 

플로이드-워셜(n의 최대 크기가 200이기 때문에 사용 가능)

def solution(n, s, a, b, fares):
    INF = int(1e9)
    graph = [[INF] * (n + 1) for _ in range(n + 1)]
    for edge in fares:
        n1, n2, cost = edge
        graph[n1][n2] = cost
        graph[n2][n1] = cost
    
    for i in range(n + 1): graph[i][i] = 0  # 자기 자신을 향한 거리는 무조건 0
    
    for via in range(1, n + 1):
        for start in range(1, n + 1):
            for end in range(1, n + 1):
                graph[start][end] = min(graph[start][end], graph[start][via] + graph[via][end])
    
    res = graph[s][a] + graph[s][b]  # 합승하지 않은 루트
    for via in range(1, n + 1):
        res = min(res, graph[s][via] + graph[via][a] + graph[via][b])  # 합승하여 이동
    
    return res

 

풀이

- start -> end 까지의 최단거리를 구하는 다익스트라 함수를 구현한 다음, 합승하지 않은 경우의 수인 res를 설정한다.

- 이후 노드 1부터 n까지 체크하면서 합승한 케이스를 다익스트라를 사용해 최소값을 갱신한 후 값을 리턴한다.

 

 

알게된 점

- 다익스트라를 구현해 곧바로 풀 수 있었던 문제였다.

- 주어진 루트를 2차원 그래프로 변환하는 것과 경로를 찾는 알고리즘을 사용해 활용하는 아이디어를 떠올리는 것이 골자였다.

- 플로이드-워셜의 구현이 확실히 쉬웠고 해당 문제는 노드의 최대 개수가 200개밖에 되지 않아 O(n^3)도 가능했었다.

- 다만 마지막에 본인이 본인 노드를 가는 케이스를 0으로 초기화하지 않는 바람에 테스트케이스3에서 계속 오류가 발생했었다.

- 여러모로 다익스트라와 플로이드-워셜 구현 연습을 할 필요성을 느끼게 해 주는 문제였다.

 

 

참고 사이트

-