2. [Python] 프로그래머스 2021 카카오 블라인드 채용 : 합승 택시 요금 - 코딩도치

안녕하세요. 코딩도치입니다~

 

오늘은 프로그래머스에 있는 2021 카카오 블라인드 채용 : 합승 택시 요금 문제를 풀어보려고 합니다!

 

위 문제는 플로이드 워셜(Floyd-Warshal) 알고리즘을 사용하여 풀어야 효율성 테스트를 통과할 수 있습니다.

 

먼저, 플로이드 워셜(Floyd-Warshal) 알고리즘에 대해서 알아보겠습니다.

 

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

 

프로이드 워셜 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘입니다.

 

그래프에서 최단 경로는 찾는 알고리즘은 다양합니다. 하지만 각각의 알고리즘이 적용될 수 있는 상황이 있기 때문에,

 

문제를 보고 적절한 알고리즘을 파악할 수 있어야합니다.

 

또다른 그래프 최단 경로 알고리즘인 다익스트라 알고리즘과 특징을 비교해보자면 다음과 같습니다.

 

다익스트라(Dijkstra)

 - 한 노드에서 다른 노드로 가는 최단 경로 구하기

 - 양수 가중치만 적용 가능

 

플로이드 워셜(Floyd-Warshal)

 - 모든 노드들 사이의 최단 경로 구하기

 - 음수 가중치에도 적용 가능

 

즉, 플로이드 워셜 알고리즘은 그래프의 모든 노드들 사이의 최단 경로를 구하는 알고리즘입니다.

 

당연히 연산량이 많기 때문에 다익스트라 알고리즘보다 느리지만 구현이 간단하다는 장점이 있습니다.

 

플로이드 워셜 알고리즘의 프로세스를 알아보도록 하겠습니다.

 

위와 같은 가중치 그래프가 주어졌을 때, 가장 먼저 해야할 것은 그래프를 표현하는 이차원 배열을 초기화하는 것입니다.

 

각각의 노드가 시작과 끝이 되었을 때, 드는 비용을 테이블로 만드는 것이죠.

 

처음에 직접 연결이 되어 있지 않아 갈 수 있는지 없는지 모르는 부분에 대해서는 INF(Infinite) 무한대의 숫자로 정의해 줍니다.

 

최소 비용을 찾는 것이기 때문에, 절대 나올 수 없는 무한대 숫자를 정의해 놓고 비교를 해 나가는 것입니다.

 

예를 들어

1번 노드 -> 2번 노드로 가는 비용 : 5

1번 노드 -> 4번 노드로 가는 비용 : 1

1번 노드 -> 3번 노드로 가는 비용 : 직접 연결되어 있지 않음 - INF

 

다음으로 각 노드를 경유지로 할 때의 시작 노드에서 도착 노드로 가는 경로를 계산하는 것입니다.

 

1번 노드를 경유지로 하는 경우로 예를 들어보겠습니다.

 

기존에 초기화를 해놓았던 그래프를 이용하여 1번 노드를 경유지로 했을 때 비용을 계산하는 것입니다.

 

예를 들어

1번 노드 -> 3번 노드로 가는 경우는 1번 노드 -> 1번 노드 -> 3번 노드로 가는 경우와 비교되는 것입니다.

 

그래서 기존에 1번 노드 -> 3번 노드의 경우보다 1번 노드 -> 1번 노드 -> 3번 노드로 가는 경우의 비용이 더 적게 든다면,

 

테이블 값을 수정하는 것입니다.

 

위 그래프에서 값이 변하는 더 직관적인 경우를 살펴보겠습니다.

 

3번 노드 -> 2번 노드로 가는 경우 처음에는 직접 연결이 되어 있지 않았기 때문에 INF값을 가지고 있었습니다.

 

하지만 1번 노드를 경유하게 되면

 

3번 노드 -> 1번 노드 -> 2번 노드로 가는 비용을 9로 계산할 수 있게 됩니다.

 

INF와 9 중에서 작은 값을 3번 노드에서 2번 노드로 가는 비용을 갖게 되는 것이죠.

 

위 과정을 모든 노드에 대해서, 즉 각 노드를 경유지로할 때를 모두 계산해주게 되면 모든 노드들 사이의 최단 경로를 구할 수 있는 것입니다.

 

다음은 파이썬으로 구현한 문제 해결 소스코드 입니다.

 

문제에서의 핵심포인트는 플로이드 워셜 알고리즘을 이용해서 모든 노드 사이의 최단 경로를 구하고,

 

브루트포스 방식으로 주어진 시작점에서 두 도착 지점에 도착하는 최소 비용을 구할 수 있다는 것입니다.

 

두 도착 지점에 가는 경우는 다음과 같이 3가지 입니다.

 - 각자 따로 타고 가는 방법

 - 어느 지점까지 같이 가고, 그 지점부터 따로 가는 방법

 - 한 도착지를 들렀다가 다른 도착지로 가는 방법

 

위 세가지 경우를 나타내는 식

 

[시작지점][경유지점] + [경유지점][도착지점1] + [경유지점][도착지점2]

 

경유지점이 시작지점이 되면 각자 따로 타고 가는 경우가 되고

 

경유지점이 도착지점이 되면 한 도착지를 들렀다가 다른 도착지로 가는 경우가 되는 것입니다.

# 2021 카카오 블라인 코딩테스트 - 합승 택시 요금

import math


def solution(n, s, a, b, fares):
    s -= 1
    a -= 1
    b -= 1
    INF = math.inf   # 무한대 표현
    answer = INF
    min_fee = [[INF for col in range(n)] for row in range(n)]

    # 자기 자신으로 가는 비용 0으로 초기화
    for i in range(n):
        min_fee[i][i] = 0

    # 주어진 비용으로 테이블 초기화
    for fare in fares:
        start, end, fee = fare
        min_fee[start - 1][end - 1] = fee
        min_fee[end - 1][start - 1] = fee

    # 플로이드 워셜 알고리즘으로 모든 노드 최단 경로 구하기
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if min_fee[i][j] > min_fee[i][k] + min_fee[k][j]:
                    min_fee[i][j] = min_fee[i][k] + min_fee[k][j]

    # 시작점(s)에서 각각의 도착지(a, b)에 도착하는데 드는 최소 비용 구하기
    for i in range(n):
        if answer > min_fee[s][i] + min_fee[i][a] + min_fee[i][b]:
            answer = min_fee[s][i] + min_fee[i][a] + min_fee[i][b]

    return answer

감사합니다.