[프로그래머스] 파이썬 _ 합승 택시 요금 (2021 KAKAO BLIND)

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

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

 

문제유형 : 최단경로 ( 다익스트라, 플로이드워셜)

 

문제풀이 :

 

• 중간지점을 k (1<= k <= n) 이라고할때, 출발지~중간지점 + 중간지점~A + 중간지점~B 의 비용중 최소가 답이다!! 생각보다 간단한 문제

 

• 즉, 모든노드에서 모든노드까지의 최단경로를 알아야하므로 나는 출발지를 모든노드로 해서 다익스트라를 총 n번 호출해서 각각의 노드를 출발점으로해서 최단경로를 answer배열에 저장하였다.

 

• 최단경로 테이블에서 현재 거리가 가장 작은 노드를 선택하는 과정에서 그냥 리스트로 풀었는데 이부분을 우선순위큐로 해결하면 시간복잡도를 로그엔까지 줄일수 있다. 

 

• 우선순위큐로도 다시 풀어볼것 -> 우선순위큐를 이용해서 풀면 방문처리를 위한 visited배열이 필요없다!

 

정답코드

- 나는 다익스트라로 풀었다. 워셜로도 풀어봐야겠다. 

def solution(n, s, a, b, fares):
    answer = [0] * (n+1)
    # s - 출발지점, a,b각각 도착지점
    graph = [ [0 for _ in range(n+1)] for _ in range(n+1)]
    INF = int(1e9)

    for i in fares:
        start, end, cost = i[0], i[1], i[2]
        graph[start][end] = cost
        graph[end][start] = cost

    for i in range(1, n+1):
        distance = [INF] * (n + 1)
        visited = [False] * (n + 1)

        answer[i] = dijkstra(i, visited, distance, graph, n)

    # 중간지점이 1~n
    result = 1e9
    for i in range(1,n+1):
        # 시작점 ~ 중간지점 + 중간지점 ~ a + 중간지점 ~ b
        result = min(result, answer[s][i] + answer[i][a] + answer[i][b])

    return result

def dijkstra(start, visited, distance, graph,n):
    #방문처리
    visited[start] = True
    distance[start] = 0

    for idx, i in enumerate(graph[start]):  # 현재노드로부터 연결된 노드를 찾음
        if i != 0:  # 연결되어있다는것
            temp = i + distance[start]  # 현재노드까지의 거리 + 현재로부터 목적지노드까지의 거리
            if temp < distance[idx]:
                distance[idx] = temp  # 더 최단거리이면 갱신

    # 시작노드를 제외한 나머지노드에서 반복
    for _ in range(n-1):
        # distance에서 방문전이면서 가장작은 노드의 인덱스를 찾는다.
        min_val = int(1e9)
        min_idx = 0
        for i in range(n+1):
            if distance[i] < min_val and not visited[i]:
                min_val, min_idx = distance[i], i

        visited[min_idx] = True

        for idx, j in enumerate(graph[min_idx]):
            if j != 0:
                temp = j + distance[min_idx]  # 현재노드까지의 거리 + 현재로부터 목적지노드까지의 거리
                if temp < distance[idx]:
                    distance[idx] = temp  # 더 최단거리이면 갱신
    return distance

- 다익스트라 + 우선순위큐 로 푼 코드 

import heapq


# n - 지점의개수, s : 출발지, a,b : 각각의 도착지, fares:간선정보
def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n + 1)]

    for i in fares:
        start, end, dist = i[0], i[1], i[2]
        graph[start].append((end, dist))
        graph[end].append((start, dist))

    INF = int(1e9)
    dist_list = [0]


    for i in range(1,n+1):
        distance = [INF] * (n + 1)
        dist_list.append(dijkstra(i, graph, distance))

    answer = INF
    for i in range(1,n+1):
        # s-i, i-a, i-b
        answer = min(answer, dist_list[s][i] + dist_list[i][a] + dist_list[i][b])
    return answer


def dijkstra(start, graph, distance):
    q = []

    # 힙에는 ( 거리, 노드) 튜플형식으로 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0


    while q:
        curr = heapq.heappop(q)
        node = curr[1]
        dist = curr[0]
        if distance[node] < dist:  # 이미 처리된것
            continue

        # 현재노드와 연결된 노드에 대해서
        # 최단거리테이블에서 연결노드의값 : 현재노드~연결노드 + 현재노드의 최단거리테이블값
        for i in graph[node]:   
            next_node = i[0]
            d = i[1]
            if distance[next_node] > dist + d:
                distance[next_node] = dist + d
                heapq.heappush(q, (dist + d, next_node))

    return distance