프로그래머스(python) - 합승 택시 요금

프로그래머스(python) - 합승 택시 요금

문제는 이것입니다.

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

이것도 경로를 구하는데 최단 경로와 비슷한 느낌을 가진 문제입니다.

다만 거리두기의 문제처럼 bfs 방식으로 문제를 푸려고 했지만 어려움을 느꼈습니다.

그래서 다른 사람의 풀이를 보면서 공부하였습니다.

https://summa-cum-laude.tistory.com/15

def solution(n, s, a, b, fares): inf = int(2e9) answer = inf # 인덱스가 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] # 출발점인 s를 기준으로 어떤 지점인 k를 거쳐 각각 a와 b로 가는 최소 비용을 탐색 for k in range(n): if answer >= (graph[s][k] + graph[k][a] + graph[k][b]): answer = (graph[s][k] + graph[k][a] + graph[k][b]) return answer if __name__ == '__main__': fares = [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] print(solution(6,4,6,2,fares))

다른 부분은 다 이해가 갔는데 플로이드-와샬이란 알고리즘이 이해가 안갔습니다.

플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단경로를 구하는데에 사용됩니다.

설명은 이 분의 게시글이 좋은 것 같습니다.

https://blog.naver.com/ndb796/221234427842

from http://cleaning-toolbox.tistory.com/72 by ccl(A) rewrite - 2021-12-22 14:26:57