📌 프로그래머스 - 합승 택시 요금

다익스트라로 풀었었는데, 플로이드-워샬로 풀어보고 싶어서 해당 알고리즘을 공부하고 적용해서 풀어봤다.

📣 플로이드-워샬 알고리즘?

모든 node 사이의 최단 경로를 찾는 탐색 알고리즘.

특정 node에서부터의 최단 경로를 찾는 다익스트라 알고리즘은 1차원 배열을 사용하지만,

플로이드-워샬은 모든 node 사이의 최단 경로를 찾기 때문에 2차원 배열을 사용한다.

📋 내 답안

def solution(n, s, a, b, fares):
    answer = 100001 * n
    M = 100001 * n
    graph = [[M for _ in range(n+1)] for _ in range(n+1)]
    # 플로이드-워셜, 초기상태 정의
    for i,j,c in fares:
        graph[i][j] = c
        graph[j][i] = c
    
    # 자기 자신은 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                graph[i][j] = 0
    
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if graph[i][j] > graph[i][k]+graph[k][j]:
                    graph[i][j] = graph[i][k]+graph[k][j]

    for i in range(1,n+1):
        answer = min(answer,graph[i][s]+graph[i][a]+graph[i][b])
    
    return answer

다익스트라로 풀었을 때는 간신히 효율성 테스트를 통과했던 케이스도 있었는데(7000ms 이상..), 플로이드-와샬로 푸니 전반적으로 완만하게 통과했다.

[참고] 📌 다익스트라+완전탐색 풀이 : 합승 택시 요금

🔮 답안 해석

플루이드-워셜 알고리즘 과정

1. 모든 노드 사이의 연결을 나타내는 graph 생성

graph = [[M for _ in range(n+1)] for _ in range(n+1)]

2. 초기상태 세팅하기 : 하나의 node에서 바로 다른 node로 갈 수 있으면 graph에 갱신하기. 그렇지 않으면 INF 상태로 놔두기

    for i,j,c in fares:
        graph[i][j] = c
        graph[j][i] = c
        
    # 자기 자신은 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                graph[i][j] = 0

3. 3중 for문으로 해당 node를 거쳐서 비용이 줄어들면 값을 갱신한다.
   (= 거쳐갈 node 설정하기)

	# k = 거쳐가는 지점
    for k in range(1,n+1):
    	# i = 시작 node
        for i in range(1,n+1):
        	# j = 끝 node
            for j in range(1,n+1):
            	# 노드 k를 거쳐가는 것이 최소비용이면 값 갱신
                if graph[i][j] > graph[i][k]+graph[k][j]:
                    graph[i][j] = graph[i][k]+graph[k][j]