programmers - 합승 택시요금

programmers.co.kr/learn/courses/30/lessons/72413

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

def solution(n, s, a, b, fares):
    INF = int(1e9)
    graph = [[INF]*n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0
    for fare in fares:
        i,j,k = fare
        graph[i-1][j-1] = graph[j-1][i-1] = k
    for i in range(n):
        for j in range(n):
            for k in range(n):
                """ graph[j][k] = min(graph[j][k],graph[j][i]+graph[i][k])  """
                # min들어가면 무조건 시간초과. for 3번에 min이면....
                if graph[j][k] > graph[j][i]+graph[i][k]:
                    graph[j][k] = graph[j][i]+graph[i][k]
    answer = INF
    for i in range(n):
        answer = min(answer,graph[s-1][i]+graph[i][a-1]+graph[i][b-1])

    return answer

min 을 사용하면 for문 3개에 min이면 무조건 시간초과가 날 수 밖에 없다.

카카오 인턴 코테를 보면서 느낀건 시간복잡도를 항상 생각하면서 코딩을 해야 한다는 것이였다.

플로이드 워셜 방법을 사용했는데 다익스트라 또한 가능할 거 같다.

플로이드 워셜은 노드에서 노드로 이동하는 가장 최소 비용을 graph 배열안에 비교하면서 기록하는 방법이다.

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

위에 부분이 플로이드 워셜의 핵심 부분이라고 할 수 있다.