[C++][백준 11404] 플로이드

[문제]

11404번: 플로이드 (acmicpc.net)

---

[문제 풀이]

플로이드-워셜(플로이드 와샬)에 대해서 알아보도록 하자!

 

해당 문제를 예시로 플로이드 와샬을 하는 방법에 대해서 알아보자.

 

문제의 조건에 맞는 행렬을 우선 만들어보자.

	2	3	1(2)	10
			2
8			1(2)	10(1)
				3
7	4

 

여기에서 가장 짧은 거리를 알아야 하니까 원소에서 중복되는 값은 짧은 값만 남겨주자.

	2	3	1	10
			2
8			1	1
				3
7	4

그러면 이제 i 에서 j 로 한번도 걸치지 않고 바로 가는 그래프에 대해서 알게 되었다. 해당 그래프를 이용해서 n번을 걸쳐서 가는 루트중에 가장 짧은 루트를 알아보자

 

i, j 에서 1을 통해서 걸쳐가는 루트에 대해서 알아보도록 하자.

[i][1] + [1][j]는 곧 i에서 j로 갈 수 있다는 의미이므로 해당 술식을 이용하자.

1을 통해서 가는 경우

	2	3	1	10
			2
8	10(8+2)		1, 9(8+1)	1, 18(8+10)
				3
7	4, 9(7+2)	10(7+3)	8(7+1)

 

2를 통해서 가는 경우

	2	3	1 3(2+1)	10 12(2+10)
			2
8	10		1 12(10 + 2)	1
				3
7	4	10	8 6(4+ 2)

3을 통해서 가는 경우

	2 13(3+10)	3	1 4(3+1)	10 4(3+1)
			2
8	10		1	1
				3
7 18(10+8)	4 20(10+10)	10	6 11(10+1)

4를 통해서 가는 경우

	2	3	1	4 4(1+3)
			2	5(2+3)
8	10		1	1
				3
7	4	10	6

5를 통해서 가는 경우

	2 8(4+4)	3 14(4+10)	1 10(4+6)	4
12(5+7)		15(5+15)	2 11(5+6)	5
8 8(1+7)	10 5(1+4)		1 7(1+6)	1
10(3+7)	7(3+4)	13(3+10)		3
7	4	10	6

 

해당 과정을 통해서 정답을 알 수가 있다.

이제 해당 과정을 코드로 바꿔보자.

*주의 사항 : 중간에 통해서 가는 곳을 가장 바깥쪽에 둬야 한다. 안 그럴 경우 모든 경우를 확인하기가 힘들다.

---

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 100000000;
int city[101][101];

void floid(int n){

    for(int k = 1;k<=n;k++){
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(city[i][j] > city[i][k] + city[k][j]){
                    city[i][j] = city[i][k] + city[k][j];
                }
            }
        }
    }

    return;
}

int main(){
    int n;
    int m;
    cin>>n>>m;
    
    fill(city[0],city[n + 1],INF);

    for(int i = 0;i<m;i++){
        int a,b,temp;
        cin>>a>>b;
        cin>>temp;
        city[a][b] = min(city[a][b],temp);
    }

    for(int i = 1;i<=n;i++){
        city[i][i] = 0;
    }

    floid(n);

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(city[i][j] == INF){
                cout<<0<<" ";
                continue;
            }
            cout<<city[i][j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}