길찾기 알고리즘(1) - 플로이드-와샬 알고리즘

플로이드-와샬 알고리즘

 플로이도-와샬 알고리즘의 기본 이론은 '중간에 경유지를 거쳐가는게 빠르다면 그 값으로 업데이트' 해주는 것입니다. 또한 이전의 다익스트라 알고리즘과의 차이라고 하면 다익스트라 알고리즘은 [ 시작지점 1개  to  여러 목적지  ] 를 구하는 알고리즘이라 모든 경로를 구할 수 없습니다. 하지만 플로이드-와샬 알고리즘의 경우 모든노드 to 모든 노드의 경로값을 구할 수 있다는 장점이 있습니다.

 구현을 하게 되면 for문이 3개가 있어 O(n^3)의 시간 복잡도를 가지게 되고 경로를 저장할 2차원 배열이 필요하기 때문에 n^2만큼의 공간 복잡도가 필요하게 됩니다.

 

말로 풀어쓰는 플로이드-와샬 알고리즘

	A	B	C
A	-	5	15
B	4	-	5
C	1	20	-

 A에서 B, C로 가는 비용이 5, 15이고 B에서 A, C로 가는게 4, 5, C에서 A, B로 가는게 1, 20이라고 하면 초기 값들은 저렇게 저장이 됩니다.

 이제 경유지를 순서대로 정해서 값을 업데이트 하면 됩니다. 먼저 경유지를 A로 지정하고 값을 업데이트 해 줍시다.

	A	B	C
A	-	5	15
B	4	-	5
C	1	6	-

 - A to A는 값이 없어 B, C로 가는 값이 업데이트 되지는 않습니다.

 - B to A는 4의 비용이 들고 B to C < B to A to C이므로 업데이트 되지는 않습니다.

 - C to A는 1의 비용이 들고 C to B > C to A to B 이므로 값이 업데이트 됩니다.

	A	B	C
A	-	5	10
B	4	-	5
C	1	6	-

 다음 경유지를 B로 잡은 뒤 이전에 업데이트된 배열을 가지고 업데이트를 하게 됩니다.

 - A to B는 비용이 5가 들고 A to C > A to B to C이므로 값이 10으로 업데이트 됩니다.

 - B to B는 값이 없어 업데이트 되지 않습니다.

 - C to B는 비용이 6이 들고 C to A < C to A to B 이므로 업데이트 되지는 않습니다.

	A	B	C
A	-	5	10
B	4	-	5
C	1	6	-

 마지막으로 경유지를 C로 잡고 업데이트 하면 됩니다.

 - A to C는 비용이 10이 들고 A to B < A to C to B 이므로 업데이트 되지는 않습니다.

 - B to C는 비용이 5가 들고 B to A < B to C to A 이므로 업데이트 되지는 않습니다.

 - C to C는 값이 없어 업데이트 되지 않습니다.

 

 이런식으로 경유지를 순서대로 지정하면서 점점 값을 줄여나가는게 플로이드-와샬 알고리즘입니다.

 

C++로 간단히 만든 소스코드

#include <iostream>
using namespace std;

int n; // 노드 수
int road[100][100];

void FloydWarshall(){
    for(int via = 1; via <= n; via++){
        for(int from = 1; from <= n; from++){
            if(!road[from][via])   continue;
            for(int to = 1; to <= n; to++){
                if(road[from][to] > road[from][via] + road[via][to])
                    road[from][to] = road[from][via] + road[via][to];
            }
        }
    }
}

 

소스코드 분석

 - for 문은 경유지 -> 출발지점 -> 도착지점 순으로 돌게 됩니다.

 - 중간중간 값이 없다고 하면(입력된 값이 없는 경우) continue를 통해 속도를 조금 높여줍니다.

    - 입력값이 없다는건 지나갈 수 없다는 뜻입니다.

 - 마지막 포문에서 경유지를 지나가는게 더 빠르다고 하면 그 값으로 업데이트 해줍니다.

 

 

플로이드 와샬을 이용한 문제들

1. 백준 11404 - 플로이드

11404번: 플로이드

 위 코드를 그대로 사용할 수 있을 정도로 기본적인 문제였습니다. 알고리즘만 알면 바로 풀이가 가능했습니다.

백준 11404 플로이드 - C++

  - 풀이

 

2. 백준 1613 - 역사

1613번: 역사

 사건의 전후관계를 따진다는 것에서 플로이드-워샬 알고리즘을 사용할 수 있었습니다.

백준 1613 역사 - C++

  - 풀이

---

22.03.04 : 소스코드 수정