Programmers: 합승 택시 요금

Posted on In

풀이

Programmers 72413: 합승 택시 요금

처음 문제를 읽고 특정 지점에서 특정 지점까지의 최소 가중치를 구해야한다고 생각했다.
최소 가중치를 출력하는 변수 l을 산출하였지만, 가장 큰 문제는 합승 유무 혹은 지점이였다.
따라서 브루트 포스 (Brute-force) 알고리즘을 통해 특정 지점까지 합승을 하였을 때의 최솟값으로 갱신해준 뒤 최종적으로는 합승을 하지 않았을 때의 값을 갱신해주어 answer를 리턴해주었다.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys

def solution(n, s, a, b, fares):
    answer = sys.maxsize
    s -= 1
    a -= 1
    b -= 1
    l = [[sys.maxsize for _ in range(n)] for _ in range(n)]
    for p1, p2, f in fares:
        l[p1 - 1][p2 - 1] = f
        l[p2 - 1][p1 - 1] = f
    for k in range(n):
        for i in range(n):
            for j in range(n):
                l[i][j] = min(l[i][j], l[i][k] + l[k][j])
    for i in range(n):
        if i == a:
            answer = min(answer, l[s][a] + l[a][b])
        elif i == b:
            answer = min(answer, l[s][b] + l[b][a])
        else:
            answer = min(answer, l[s][i] + l[i][a] + l[i][b])
    answer = min(answer, l[s][a] + l[s][b])
    return answer