Programmers - 합승 택시 요금

문제링크

나의 풀이(오답)

def DFS(ca, cb, ssum, a, b, n):
    global result

    if ca == a and cb == b:
        result = min(result, ssum)
        return

    for k in (1, n):
        if not G[ca][k] == 0 and not visited_a[k] == 1:
            na = k
            visited_a[na] = 1
            ssum += G[ca][na]
        if not G[cb][k] == 0 and not visited_b[k] == 1:
            nb = k
            visited_b[nb] = 1
            ssum += G[cb][nb]
        if na == nb and ca == cb:
            ssum -= G[cb][nb]
        DFS(na, nb, ssum, a, b, n)
    print(result)


def solution(n, s, a, b, fares):
    global G, visited_a, visited_b, result
    result = 0

    G = [[0] * (n + 1) for _ in range(n + 1)]
    visited_a = [0] * (n + 1)
    visited_b = [0] * (n + 1)

    for value in fares:
        G[value[0]][value[1]] = value[2]
        G[value[1]][value[0]] = value[2]

    DFS(s, s, 0, a, b, n)

• 프로그래머스 특성상 기본으로 지역변수를 사용하게 된다.
  • global하게 사용되는 변수들을 미리 생각해 전역 처리를 한다.

다른 풀이

import heapq

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

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[j][k] > d[j][i] + d[i][k]:
                    d[j][k] = d[j][i] + d[i][k]

    minv = 40000002
    for i in range(n):
        minv = min(minv, d[s-1][i]+d[i][a-1]+d[i][b-1])
    return minv

• 경로의 값을 최솟값으로 계속 바꾸어주는 로직이 많이 사용된다.