[프로그래머스 level3 합승 택시 요금] 최단 경로 구하기(ft. 다익스트라, 플로이드 워셜)

해결해야하는 문제는 다음과 같았다.

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

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

 

인접행렬 형식으로 그래프를 저장한 후, '플로이드 워셜' 알고리즘을 활용하는 아이디어를 바탕으로 작성한 코드는 다음과 같다.

def solution(n, s, a, b, fares):
    INF = int(1e9)
    answer = INF
    fare_graph = [[INF]*(n+1) for i in range(n+1)]
    for i in range(1,n+1):
        fare_graph[i][i] = 0

    for st,d,c in fares :
        fare_graph[st][d] = c
        fare_graph[d][st] = c

    for k in range(1,n+1):
        for a1 in range(1,n+1):
            for b1 in range(1,n+1):
                fare_graph[a1][b1] = min(fare_graph[a1][b1], fare_graph[a1][k] + fare_graph[k][b1])

    for i in range(1,n+1):
        c = fare_graph[s][i] + fare_graph[i][a] + fare_graph[i][b]
        if c < answer :
            answer = c
    return answer

하지만 이는 정확도 테스트는 모두 통과하지만 효율성 테스트에서 26번을 시간 초과로 통과하지 못하였다.

 

 

 

따라서 다익스트라 알고리즘을 활용하는 방법을 생각해보았다.

 

인접 리스트 형식으로 그래프를 저장한 후, '다익스트라' 알고리즘을 활용하였다.

이렇게 하니, 확인하고자 하는 지점들에 대해서만 최단 경로를 확인하여 효율성 테스트를 통과할 수 있는 것 같았다 !

INF = int(1e9)
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node(distance, visited,n):
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드 (인덱스 )
    for i in range(1,n+1) :
        if distance[i] < min_value and not visited[i] :
            min_value = distance[i]
            index = i

    return index

def dijkstra(start,n,graph):
    # 시작 노드에 대해서 초기화
    visited = [False] * (n+1)
    # 최단 거리 테이블을 무한으로 초기화
    distance = [INF] * (n+1)
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]

    # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node(distance,visited,n)
        visited[now] = True

        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]] :
                distance[j[0]] = cost


    return distance

def solution(n, s, a, b, fares):
    answer = INF
    fare_graph = [[] for i in range(n+1)]
    for st,d,c in fares :
        fare_graph[st].append((d,c))
        fare_graph[d].append((st,c))

    common_distance = dijkstra(s,n,fare_graph)
    a_distance = dijkstra(a,n,fare_graph)
    b_distance = dijkstra(b,n,fare_graph)

    for i in range(1,n+1):
        c = common_distance[i] + a_distance[i] + b_distance[i]
        if c<answer:
            answer = c

    return answer