[프로그래머스/Python] Level 3_합승 택시 요금

📌문제 유형

최단거리(플로이드 워셜)

 

📌문제

프로그래머스

 

 

📌나의 문제풀이

def solution(n, s, a, b, fares):
    INF = 10000000
    answer = INF
    maps = [[INF] * (n+1) for _ in range(n+1)]
    
    for i in range(n+1):
        for j in range(n+1):
            if i == j:
                maps[i][j] = 0
    
    for node1, node2, fare in fares:
        maps[node1][node2] =  fare
        maps[node2][node1] =  fare

        
    for k in range(n+1):  # 거치는 점
        for i in range(n+1):  # 시작 점
            for j in range(n+1):  # 끝 점
                maps[i][j] = min(maps[i][k] + maps[k][j],maps[i][j])

    for t in range(n+1):
        temp = maps[s][t] + maps[t][a] + maps[t][b]
        answer = min(temp, answer)
        
    return answer

 

📌다른사람의 문제풀이

- 다익스트라

[프로그래머스 LV 3] 합승 택시요금 (파이썬/python)

import heapq


def solution(n, s, a, b, fares):
    INF = 10000000
    answer = INF
    graph = [[] * (n + 1) for _ in range(n + 1)]

    for f in fares:
        node1, node2, fee = f
        # node1 - > node2 가는 요금이 fee
        graph[node1].append((node2, fee))
        # node2 - > node1 가는 요금이 fee
        graph[node2].append((node1, fee))

    def dijkstra(s):
        q = []
        # 최단거리 테이블을 무한으로 초기화
        distance = [INF] * (n + 1)
        # 거리(금액), 노드번호 순서
        heapq.heappush(q, (0, s))
        # 시작노드로 가는 최단거리는 0
        distance[s] = 0

        while q:
            dist, now = heapq.heappop(q)
            # 현재 노드가 이미 처리된 노드면 무시
            if distance[now] < dist:
                continue
                
            for g in graph[now]:
                cost = dist + g[1]
                if cost < distance[g[0]]:
                    distance[g[0]] = cost
                    heapq.heappush(q, (cost, g[0]))
        return distance

    distance_list = [[]] + [dijkstra(i) for i in range(1, n + 1)]

    for i in range(1, n + 1):
        answer = min(distance_list[s][i] + distance_list[i][a] + distance_list[i][b], answer)

    return answer

 

📌리뷰

- 최단거리 작성할 때 DFS말고 플로이드워셜, 다익스트라 있음을 기억하기!!!!!

- 플로이드 워셜 초기값 INF, 동일 위치인 경우 0으로 수정하기