1. 문제 설명

합승 택시 설명

2. 문제 분석

노드 별 최단 거리를 구해 특정 구간 c를 경유해 a, b에 도착한 경로별 거리를 구하자.

1. 플로이드 워셜 알고리즘을 통해 각 노드에서 (자신을 포함한) 모든 노드로 향하는 최단 거리를 구한다.
2. 자기 자신을 0으로, 인접하지 않은(즉 이어진 간선이 없는) 노드는 INF 값으로 초기화하자. 이때 INF는 모든 간선을 경유한 최댓값보다 커야 한다.
3. i번 노드에서 j번 노드로 향하는 거리가 k번 노드를 경유한 거리보다 길다면, 곧바로 직진하는 것보다 k번 노드를 경유해야 한다. 즉, if nodes[i][j] > nodes[i][k] + nodes[k][j] then update or keep
4. 플로이드-워셜 알고리즘을 통해 i번 노드에서 j번 노드로 향하는 최단 거리가 구해졌다. s ▷ c, c ▷ a, c ▷ b를 통해 세 노드를 모두 거치면서 그 합이 최소인 방법을 찾자. 즉 어떤 노드까지 a, b가 같이 갔을 때 최단 거리인지 구해야 한다.

• 만일 시작 노드 s에서 곧바로 헤어지는 게 더 짧다고 하더라도 본 식은 유효하다. 플로이드-워설 알고리즘에서 자기 자신으로 향하는 거리는 0이기 때문에, nodes[s][s] + nodes[s][a] + nodes[s][b]으로 구할 수 있기 때문이다.

3. 나의 풀이

def solution(n, s, a, b, fares):
    INF = 100001*n
    # 요금 최댓값 100000
    nodes = [[INF for _ in range(n+1)] for _ in range(n+1)]
    for tail, head, cost in fares:
        nodes[tail][head] = cost
        nodes[head][tail] = cost
    for i in range(n+1):
        for j in range(n+1):
            if i == j: nodes[i][j] = 0
    # 플로이드-워셜 알고리즘 사용 -> 모든 노드에 대한 각 노드의 최단 거리
    for k in range(n+1):
        for i in range(n+1):
            for j in range(n+1):
                if nodes[i][j] > nodes[i][k] + nodes[k][j]:
                    nodes[i][j] = nodes[i][k] + nodes[k][j]
    
    upto_c = [0]*(n+1)
    # s -> i, i -> a + i -> b 최단 거리, 'i'번 노드까지 동승 후 따로 간다.
    for i in range(n+1):
        upto_c[i] = nodes[s][i] + nodes[i][a] + nodes[i][b]
    

• BFS, DFS만이 아니라 노드 별 거리를 구하는 플로이드-워셜, 다익스트라, 크루스칼 등 그래프 관련 알고리즘은 능숙히 사용할 수 있게 사용 방법과 구현 방식을 익히자!