[프로그래머스] 합승 택시 요금 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

 

n이 200으로 작아서 플로이드 와샬로 풀었다.

 

풀이는 생각보다 너무 간단했다.

플로이드 와샬로 모든 점끼리 최단거리를 구해놓는다.

그리고 모든 점에서 시작해서 s,a,b 까지의 거리를 합한 것 중 최솟값을 찾으면 된다.

 

 

근데 효율성에서 계속 시간초과가 났었다. 

문제는 min 함수였다.

원래 플로이드 와샬 부분의 최솟값을 갱신하는 부분에서

                elif cost_board[i][j] > cost_board[i][k] + cost_board[k][j]:
                    cost_board[i][j] = cost_board[i][k] + cost_board[k][j]

그냥 조건문으로 교체하였다.

원래는

                    cost_board[i][j] = min(cost_board[i][j], cost_board[i][k] + cost_board[k][j])

이렇게 min 함수를 사용했었는데 이 부분에서 시간을 많이 잡아 먹는것 같다.

조건문과 min함수 차이가 시간으로 두배정도 차이가 났다.

min함수가 내부적으로 어찌 되어있는지 잘모르겠지만 min이나 max 함수도 생각보다 시간을 잡아 먹는 듯하다.

좀 더 알아봐야할 점이다.

 

혹시 알고계신분 있다면 댓글 부탁드립니다.

 

INF = 9876543210

def solution(n, s, a, b, fares):
    cost_board = [[INF] * (n + 1) for _ in range(n + 1)]

    for x, y, cost in fares:
        cost_board[x][y] = cost
        cost_board[y][x] = cost

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i == j:
                    cost_board[i][j] = 0
                elif cost_board[i][j] > cost_board[i][k] + cost_board[k][j]:
                    cost_board[i][j] = cost_board[i][k] + cost_board[k][j]

    answer = INF
    for start in range(1,n+1):
        answer = min(answer, cost_board[start][s]+cost_board[start][a]+cost_board[start][b])
    return answer