[코테 알고리듬] 플로이드 워셜 알고리듬 C++

 

목차

0. 서론

1. 알고리듬 설명

2. 백준 추천 문제 및 코드

---

0. 서론

 플로이드 워셜(Floyd-Warshall) algorithm은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리듬이다. 시간복잡도는 O(V^3)이다. 필자가 정보충이라 서론인 겸에 기술하지만, 플로이드 워셜은 이 알고리듬 개발자인 "로버트 플로이드"와 "스티븐 워셜"이 개발했고, 이후에 로버트 플로이드는 튜링상을 받았다. 

 

 "가능한 모든 노드쌍에 대해 최단거리"를 구하는 알고리듬을 만들어 낸 이유는 사실 오늘날 코딩테스트를 보는 우리에게 난이도를 선사하기 위함은 아니고, 통신 네트워크관계를 분석하기 위해 만들어진 알고리듬이다.

 이 알고리듬을 개발한 시기는 1960년대 초반인데, 당시에 미국 일부지역에 흩뿌려져 있는 네트워크 관계망에서 전체 노드간 최소 지연/비용을 한번에 계산해서 "라우팅 기준표"를 만들기 위해 쓰였다.

 

중앙에서 전체 네트워크를 알고있고, 모든 노드간 최적 경로와 지연시간, 그리고 도달 가능 여부까지 알 수 있기에, 패킷이 도착할때마다 계산하거나 여부를 아는 것이 아니라, 한번 계산해 두면 O(1)로다가 뽑아다 쓸 수 있기에 사용했던 것 같다. 이와 관련해서는 ARPA(미국 국방부 산하 고등연구계획국) 의 ARPANET의 패킷 교환 네트워크를 보면 알 수 있다. 알파넷인지 아르파넷인진 모르겠는데, 영어로 검색하는 편이 더 잘 나온다.

1970's ARPANET. https://www.reddit.com/r/MapPorn/comments/dory5m/arpanet_forerunner_to_the_internet_was_first_used/?tl=ko

 

 

 

암튼, 코딩테스트에서 플로이드는 잘 안나오는 듯 하지만 이렇게 시간써서 기술하는 이유는,

사실 원리만 기억하고 있다면 간단하게 풀 수 있는 문제지만, 기억이 안난다면 다음을 기약할 수 밖에 없게되는 알고리듬이기에 필자의 복습 차 첫 알고리듬 포스팅으로 소개 한다.

 

1. 알고리듬 설명

 서론에서 본 ARPANET의 복잡한 네트워크 관계를 생각하고 있다면, 그것을 하나의 테이블로 만드는게 맞다. 

왼쪽과 같이 간단한 그래프가 있다고 가정할 때, 오른쪽의 표 그 cost를 미리 계산하는 방법이다. 

 

여담이지만, 필자는 블로그 그림 편집을 figma로 하는데, 여기에는 정말 끔찍하게도 표가 없다. 가시성은 양해 바란다.

 

 

우선, 본인 노드에서 본인으로 가는 cost는 0이고, 현재 그래프에서는 모든 수를 한번에 갈 수 있으니, 최단거리를 고려하지 않고 코스트를 계산한다면,

이렇게 대칭적인 표가 나온다.

하지만, 일부 경우는 다른 노드를 경유해 가는 경우가 더 cost가 적은 경우가 발생한다.

이를테면, 2 - 4 인 경우에는, 일직선으로 가면 8 cost가 발생하지만, 3을 거치게 되면 5 + 2에서 7의 cost만으로 접근할 수 있기 때문이다. 

 

이렇게, 빨간색으로 바뀐 부분이, 더 빠른 경로를 찾아 바꾼 경우다.

 

이제 이러한 경우를 채우면 되는데, 이를 3중 for문으로 구현한다.

#define INF 1e9

int N;
vector<vector<int>> table;
vector<vector<int>> costs;


void main() {
	int a,b,c;
	cin >> N;
    
    table.resize(N+1, vector<int>(N+1, INF); 
    costs.resize(N+1, vector<int>(N+1, INF); 
    
    for(int i = 0; i < N; ++i) {
    	cin >> a >> b >> c;
        table[a][b] = min(c, table[a][b]);
        table[b][a] = min(c, table[b][a]);
    }
    
    for(int k = 1; k < N+1; ++k) {
    	for(int i = 1; i < N+1; ++i) {
        	for(int j = 1; j < N+1; ++j) {
                table[i][j] = min(table[i][k] + table[k][j] , table[i][j]);
            }
        }
    }

	return 0;
}

 

 탭이 좀 이상한데에 들어가있는데, 이건 tistory 코드블럭에서 코드를 쓰게 되면 오류로 탭이 들어가는 듯 하다. 

 또한, INF에서 1e9를 사용한 이유는, min에서 더하기 할때, 0x7fffffff을 쓰면, overflow가 발생하기 때문이다.

 또한, 입력에서 min을 쓰는 이유 또한, 같은 방향에 대해 여러 간선이 존재할 수 있기 때문이다.

 

for문의 문자 순서에 주의해야한다!

플로이드의 의도는,

1. 직접 연결된 간선만 알고있을 때,

2. 다른 지점을 경유하는 경우가 더 효율적일때

3. 해당 지점을 경유한다.

 

이런 사고이기 때문에,

위 코드에서 경유지인 k를 경유지로 삼을 때, "i에서 j로 가는 경우"에 수혜를 받을 수 있는지 계산하

는 알고리즘이다.

 

참고로 기술하자면, 위 코드에서 i, j, k 순으로 작성하여, "i에서 j로 갈 때, k를 경유해도 되는가?"를 두고 코딩을 하게되면, 이 로직을 두번 이상 돌려야하는 불상사가 발생하는데,

 

만일 위의 코드가 경우 A, " i에서 j로 갈 때, k를 경유해도 되는가?"가 경우 B라고 가정했을 때,

경우 A는 경유지를 기준으로 시작점과 끝점을 계산하기에, 모든 경우에 대해 빠짐없이 계산할 수 있으나,

 

경우 B는 "새로운 경유지가 뚫리며 발생하는 새로운 경우"를 계산하지 못하기 때문이다.

 

 

 

 

경로 복원에 대해서는 다음 글에서 이어서 기술하겠다.

 

(링크 첨부 예정)

 

2. 백준 추천문제 및 코드

https://www.acmicpc.net/problem/11403

 

실버 문제인데, 한번 풀어보며 감을 익혀보고,

 

 

https://www.acmicpc.net/problem/11404

 

골드 하위권 문제를 통해 table을 짜보는 연습 후에 

 

 

https://www.acmicpc.net/problem/11780

 

조금 어려운 플로이드까지 풀면 될 듯 하다.

각 문제에 대해서도 풀이를 올릴 예정이다.

 

 

 

 

---

26.02.11 집필