2021 KAKAO BLIND RECRUITMENT 합승 택시 요금 Lv. 3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72413

파이썬 소스: https://bit.ly/4a5vkUU

 

합승구간은 잠시 후에 알아 보겠습니다. 지금은 어떤 지점에서 다른 지점까지 갈 수 있는 길이 1개 이상 있고, 그 중에 비용이 가장 낮은 길을 찾는 라우팅 알고리즘부터 찾아보겠습니다. 이 문제는 플로이드 워셜, 다익스트라 두가지 모두 사용해서 문제를 풀 수 있습니다.

문제에서 지점의 개수가 200 이하로 주어지기 때문에, 플로이드 워셜 알고리즘을 사용해서, 모든 지점에서 모든 지점으로 가는 최적의 이동비용을 먼저 구하겠습니다.

플로이드 워셜 알고리즘의 시간 복잡도는 n ** 3이고, 200 ** 3 해도, 8 * 10 * 6임으로 10 ** 9 보다 작아서, 시간내에 문제를 풀 수 있습니다.

map = [[INF for _ in range(n + 1)] for _ in range(n + 1)]

모든 지점간에 연결을 표시할 map 리스트를 만들어 주고, 모두 연결이 끊어저 있는 -1 상태로 초기화 해주겠습니다.

for fr, to, fee in fares:     map[fr][to] = fee     map[to][fr] = fee

이동할 수 있는 지점마다, 이동 비용 fee를 저장합니다.

for i in range(1, n + 1):     map[i][i] = 0

같은 지점의 이동 비용은 0으로 초기화 해주겠습니다.

for mid in range(1, n + 1):     for bgn in range(1, n + 1):         for end in range(1, n + 1):             if map[bgn][mid] != -1 and map[mid][end] != -1:                 if map[bgn][end] == -1:                     map[bgn][end] = map[bgn][mid] + map[mid][end]                 elif map[bgn][end] > map[bgn][mid] + map[mid][end]:                     map[bgn][end] = map[bgn][mid] + map[mid][end]

플로이드 워셜 알고리즘을 사용해서, 모든 지점에서 모든 지점으로 가는 최소 비용을 구해서, map 리스트에 저장합니다.

answer = map[s][a] + map[s][b]

출발 지점 s 에서부터 a, b지점으로 이동하는 값을 answer에 저장합니ㅏㄷ.

for mid in range(1, n + 1):     if map[s][mid] != -1 and map[mid][a] != -1 and map[mid][b] != -1:         local_answer = map[s][mid] + map[mid][a] + map[mid][b]         answer = min(answer, local_answer)

지점 s 부터 mid 까지가 합승하는 구간이구요, mid 부터는 a, b가 각자 이동하는 비용을 계산해서, 최소 비용을 리턴하면, 이문제의 답을 구할 수 있습니다.

 

궁금한 문제/질문은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

from typing import List def solution(n: int, s: int, a: int, b: int, fares: List):     INF = -1     map = [[INF for _ in range(n + 1)] for _ in range(n + 1)]     for fr, to, fee in fares:         map[fr][to] = fee         map[to][fr] = fee     for i in range(1, n + 1):         map[i][i] = 0     for mid in range(1, n + 1):         for bgn in range(1, n + 1):             for end in range(1, n + 1):                 if map[bgn][mid] != -1 and map[mid][end] != -1:                     if map[bgn][end] == -1:                         map[bgn][end] = map[bgn][mid] + map[mid][end]                     elif map[bgn][end] > map[bgn][mid] + map[mid][end]:                         map[bgn][end] = map[bgn][mid] + map[mid][end]     answer = map[s][a] + map[s][b]     for mid in range(1, n + 1):         if map[s][mid] != -1 and map[mid][a] != -1 and map[mid][b] != -1:             local_answer = map[s][mid] + map[mid][a] + map[mid][b]             answer = min(answer, local_answer)     return answer