[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘(ft.파이썬)

🚩 플로이드 와샬 알고리즘 파이썬 구현

플로이드 와샬은 다익스트라 알고리즘과 같이 최단거리 혹은 최소비용을 구하는 알고리즘입니다.

플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 노드에서 다른 모든 노드들까지의 최소 거리(혹은 최소비용)을 구하기 때문에 "어딘가를 경유한다."라는 조건이 주어질 때, 사용을 고려하기 좋은 알고리즘 입니다.

 

다만, 출발점(s), 도착지점(e), 경유지(p)에 모든 노드를 고려해야하므로 시간 복잡도는 O(N^3)으로 큰 편 입니다.

즉, 문제에서 주어진 노드(N)의 최댓값을 고려해 미리 계산해 사용할 가치가 있는 알고리즘인지 고려해봐야합니다.

✏️ 플로이드 와샬 알고리즘

위 그림의 경우는 출발지점이 1번 노드, 도착지점이 4번 노드인 경우 입니다.

 

1 -> 4로 가는게 경유지 없이 간다면 비용은 4가 들게됩니다.

만약 경유지를 선택하게 될 때, 2번을 경유지로 선택한다면 총 비용은 3(2 + 1)이고 3을 경유지로 선택한다면 비용은 2(1 + 1)이 됩니다.

따라서 위 그림의 최소 비용(혹은 최단 거리)는 1 -> 3 -> 4를 선택한 2가 됩니다.

이제부터 1 -> 4로 이동할 때 발생하는 최소비용은 2라는 것을 알 수 있습니다.

 

플로이드 와샬은 이처럼 모든 노드를 방문해서 다른 노드까지의 최소비용을 계속 갱신해주면서 모든 노드에서 모든 노드까지(몇 번을 경우하는지 상관없이) 최소 비용을 알아낼 수 있습니다.

 

✏️ 플로이드 와샬 알고리즘 코드(파이썬)

cost = [[INF] * n for _ in range(n)]    # INF로 구성된 n x n 행렬, 노드끼리의 최소 비용을 담을 배열

for i in range(n):  # 자기자신 -> 자기자신의 비용은 0이므로 초기화 해준다.
	cost[i][i] = 0

# 플로이드 와샬
    for k in range(n):  # 경유지
        for j in range(n):  # 도착지
            for i in range(n):  # 출발지
                # 현재 i -> j까지드는 비용이 i -> k -> j의 비용보다 비싸다면 더 저렴한 비용으로 갱신
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

여기서 INF는 중간 값으로 주어진 나올 수 있는 값보다 큰 값으로 세팅합니다.

cost 배열은 출발지점 -> 도착지점 까지의 비용을 담아 놓을 2차원 배열 입니다.

 

출발점, 도착점, 경유지를 모두 탐색하는 3차원 for문을 돌면서 현재의 비용(i -> j)보다 k를 경우하는 (i -> k -> j) 비용이 더 저렴하다면 갱신해 주면 플로이드 와샬 구현이 완료 됩니다.

 

이때, 경유지를 기준으로 모든 경우(출발, 도착)을 확이해야하므로 최상단 for문에는 경유지(k)가 와야합니다.

그렇지 않을 경우, 모든 경우에서 제대로 갱신되지 않을 수 있습니다.

✏️ 플로이드 와샬 알고리즘 문제 풀어보기(2021년 카카오 신입 채용 코딩 테스트)

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

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

플로이드 와샬 알고리즘을 구현해야하는 문제인 2021년 카카오 신입 채용 코딩테스트 문제를 가져왔습니다.

 

📝 전체 코드

# 합승 택시
# 플로이드 마샬
def solution(n, s, a, b, fares):
    INF = 200 * 100000 + 1  # 최대 비용
    cost = [[INF] * n for _ in range(n)]    # INF로 구성된 n x n 행렬, 노드끼리의 최소 비용을 담을 배열

    for i in range(n):  # 자기자신 -> 자기자신의 비용은 0이므로 초기화 해준다.
        cost[i][i] = 0

    for f in fares:
        start_node = f[0] - 1   # 노드의 번호가 1부터 주어지므로 index를 맞추기 위해서 1을 빼준다.
        end_node = f[1] - 1
        price = f[2]
        # 입력으로 주어진 출발점 <-> 도착점의 비용들을 대입해준다.
        cost[start_node][end_node] = price
        cost[end_node][start_node] = price

    # 플로이드 와샬
    for k in range(n):  # 경유지
        for i in range(n):  # 출발점
            for j in range(n):  # 도착점
                # 현재 i -> j까지드는 비용이 i -> k -> j의 비용보다 비싸다면 더 저렴한 비용으로 갱신
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

    answer = INF
    # 모든 경유지를 탐색하며 최소 요금을 갱신
    for k in range(n):
        answer = min(answer, cost[s - 1][k] + cost[k][a - 1] + cost[k][b - 1])

    return answer