[KakaoSolving] 2021 카카오 블라인드 채용 - 합승 택시 요금 [Level3]

문제 설명은 생략하겠습니다. 링크를 클릭하세요.

문제 링크

입출력 예

유형

• 다익스트라
• 플로이드 워셜

나의 풀이

풀이

A와 B가 헤어지기 전의 지점을 C라고 했을 때,
S -> C로 가는 경로 + C -> A로 가는 경로 + C -> B로 가는 경로를 구한다.
각 지점의 최소 경로를 구하는 방법은 다익스트라와 플로이드 워셜을 이용했다.
각 알고리즘에 대한 내용은 최단경로(다익스트라, 플로이드워셜)

해결 1

가중치가 있는 최소 비용 경로를 찾는 문제로, 다익스트라로 해결했다.

해결 2

노드의 개수가 200개 이하이므로 플로이드 워셜을 이용하여 해결했다. (노드 개수 500개 미만)

코드

• 다익스트라

import heapq
INF = int(1e9)
def dijkstra(start, destination, graph):
    q = []
    distance = [INF]*(len(graph))
    distance[start]= 0
    heapq.heappush(q, (0, start))
    
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost_ = dist + i[1]
            # 현재 노드 꺼쳐서 다른 노드 이동하는 거리 더 짧은 경우
            if cost_ < distance[i[0]]:
                distance[i[0]] = cost_
                heapq.heappush(q, (cost_, i[0]))
    return distance[destination]

def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n+1)]
    for i in fares:
        source, destination, cost = i[0], i[1], i[2]
        graph[source].append([destination, cost])
        graph[destination].append([source, cost])
    min_cost = INF
    for i in range(1, n+1):
        min_cost = min(min_cost, dijkstra(s, i,graph) + dijkstra(i, a,graph)+ dijkstra(i, b,graph))
    return min_cost

• 플로이드 워셜

def solution(n, s, a, b, fares):
    graph = [ [20000001 for _ in range(n)] for _ in range(n)]
    for x in range(n):
        graph[x][x] = 0
    for x, y, c in fares:
        graph[x-1][y-1] = graph[y-1][x-1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                # graph[j][k] = min(graph[j][i] + graph[i][k], graph[j][k])
                if graph[j][k] > graph[j][i] + graph[i][k]:
                    graph[j][k] = graph[j][i] + graph[i][k]

    min_ = int(1e9)
    for i in range(n):
        min_ = min( min_, graph[s-1][i] + graph[i][a-1] + graph[i][b-1] )
    return min_