2021 카카오 블라인드 채용 '합승 택시 요금' 문제 풀이

2021 카카오 블라인드 채용 '합승 택시 요금' 문제 풀이

문제

https://programmers.co.kr/learn/courses/30/lessons/72413?language=python3

출발점을 s, A의 도착지점을 a, B의 도착지점이 b, 중간에서 갈라질 수 있는 임의의 지점을 i라고 할 때

택시 요금의 식을 (s → i)+(i → a)+(i → b)과 같이 유도할 수 있으며 최종적으로 i를 계속 업데이트하면서 예상 최저 택시 요금 을 구할 수 있습니다.

i를 출발노드로 두는 경우를 한 번에 구하기 위해 모든 노드 쌍에 대한 최단경로를 구하는 플로이드-워셜 알고리즘을 사용하여 다음과 같이 시도했습니다.

풀이(플로이드-워셜 알고리즘)

import sys inf=sys.maxsize def solution(n, s, a, b, fares): s, a, b = s - 1, a - 1, b - 1 Mat = [[inf] * n for _ in range(n)] for i in range(n): Mat[i][i]=0 for i in fares: #Mat에 간선 간 비용에 대한 초기 정보 입력 Mat[i[0]-1][i[1]-1]=i[2] Mat[i[1]-1][i[0]-1]=i[2] for i in range(n): #플로이드-워셜 알고리즘 for j in range(n): for k in range(n): if j==k: Mat[j][k]==0 else: Mat[j][k]=min(Mat[j][k],Mat[j][i]+Mat[i][k]) cost=inf for i in range(n): #출발노드s로 시작하여 갈라지는 경우에 대한 비용을 확인하기 위함. cost=min(cost,Mat[s][i]+Mat[i][a]+Mat[i][b]) return cost

플로이드-워셜 알고리즘 같은 경우 시간복잡도가 O(V^3)이다 보니 다음과 같이 소수의 케이스에 한해 시간 초과가 발생했습니다.

다음은 다익스트라 알고리즘을 이용한 풀이입니다.

(s → i)+(i → a)+(i → b) 식이 도출된다면 각각의 노드 쌍에 대해 다익스트라 알고리즘으로 최단거리를 구하는 방식입니다.

풀이(다익스트라 알고리즘)

import sys import heapq inf = sys.maxsize graph = [[]] def dijkstra(s, e): #s=출발점 e=도착점 global graph table = [inf]*(N+1) table[s] = 0 pq = [[0, s]] while pq: cost, node = heapq.heappop(pq) if table[node] < cost: continue for n,c in graph[node]: c += cost if c < table[n]: table[n] = c heapq.heappush(pq, [c, n]) return table[e] def solution(n, s, a, b, fares): global graph,N N=n graph = [[] for _ in range(n + 1)] for i, j, k in fares: graph[i].append((j, k)) graph[j].append((i, k)) cost = inf #예상 택시 요금 for i in range(1,n+1): cost = min(cost, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b)) return cost

from http://lbdiaryl.tistory.com/185 by ccl(A) rewrite - 2021-10-19 18:00:22