플루이드 와샬 #All-pairs-shortest-path #Dijkstra

저번에 못풀었던 플루이드-와샬 알고리즘, 다시 보니 매우쉽다.!!

생각보다 매우 신박한 알고리즘이다. 생긴 것도 매우 단순하다. 절대 잊지 말자. floyd니까 ForLoopOnly3으로 외우자..ㅎㅎㅎ

플루이드-와샬 코드

for(int k=1; k<=N; k++){ 

for(int i=1; i<=N; i++){

for(int j=1; j<=N; j++){

if(Map[i][j] > Map[i][k] + Map[k][j]) 

Map[i][j] = Map[i][k] + Map[k][j];

via[k][j] = k;

}}}

k번째 노드를 들리면서 update해준다. (relex와 다르다. 당장 옆노드만 보는 게 아니라 history가 업데이트된다.) 

(1) 만약 1-3까지의 최단루트가 1-5-2-3 일 경우, detect하지 못하면 어쩌하나 하는 마음이 있지만

사실 k=2일 때, 5-2-3이 먼저 형성되어 5-3이 되어버리고, 나중에 k=5일 때, 1-5-3이 형성되어 1-5-2-3을 완성해주기 때문에 걱정 없다. 

이럴 경우, via에는 via[1][3] = 2, via[1][2] = 5, via[1][5] = 1 이다. 역으로 1->1->5->2->3 이렇게 갈 수 있다는 것을 알게된다.

(2) 만약 도중에 cycle이 형성되더라도 상관없다. 

via를 통하여 경로도 알아낼 수 있다.

조건: 유향그래프, 최단거리 혹은 연결여부, 모든점->모든점

Time Complexity : O(V^3), //Edge가 빽빽할 때 사용하기 좋다.

#1. 저울

문제번호: 10159

분류: 플루이드 와샬 알고리즘

비고: dfs로도 가능, #1613_역사 문제와 동일

저울 문제에서 각각 두물건이 무거운지 가벼운지의 관계를 알 때, 임의의 두 물건의 무겁거나 가벼운지 알 수 없는 경우에 대해서 구하는 문제였다.

유향 그래프 문제라고 해석할 수 있다.

DFS풀이

각 물건을 Doubly-linked Graph로 구현

struct NODE{

vector<int> cmpW[2]; // 가벼운것: 0, 무거운것: 1

} Node[101];

int SlaveExplore(int n, int direction){ //본인과, 본인 밑에 달린 노드갯수를 리턴해주는 함수

if(Node[n].cmpW[direction].empty()){

return 1;

}

int cnt = 1;

for(auto& next : Node[n].cmpW[direction]){

cnt += SlaveExplore(next, direction);

}

return cnt;

}

direction 각각 0, 1 일때를 실행하면 된다.

Time Complexity : O(E) * V = O(VE)

Floyd보다 훨씬 빠르다!ㅎㅎ

관련문제

1238_파티_다익스트라 //플루이드지만 다익스트라2번 돌리는게 더 빠른

1389_케빈베이컨_플루이드

1613_역사_플루이드/dfs

10159_저울_플루이드/dfs

11403_경로찾기_플루이드

11404_플로이드_플루이드