(c++) 플로이드 워셜 알고리즘 11404번: 플로이드

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

11404번: 플로이드

 

---

 

 

플로이드-워셜 알고리즘

 

 

앞서 살펴본 다익스트라 알고리즘은 하나의 시작점에 대해서 최단 경로를 살펴보는 알고리즘이다.

 

정점 전체에 대해서 최단 경로를 살펴보려면 각 정점마다 다익스트라 알고리즘을 적용해야 할까?

 

그래서 나왔다! 플로이드-워셜 알고리즘

 

정점의 개수가 V라고 한다면

|V| x |V|  행렬을 만들고 자기 자신을 0으로 초기화한다. dist[v1][v1] = 0

그 외 나머지는 무한 INF로 초기화한다.

 

삼중반복문으로 모든 정점들 사이에 K라는 정점을 추가해서

최소가 되는 값으로 교체하는 알고리즘이다.

 

점화식으로 살펴보면

 

$$ \mathrm{D}_{ab} = min(\mathrm{D}_{ab}, \mathrm{D}_{ak} + \mathrm{D}_{ka}) $$

 

 

코드는 미리 저장된 간선 정보를 담은 graph[V+1][V+1] 를 이용하면 이렇게 된다.

for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
        }
    }
}

 

 

11404번: 플로이드

 

플로이드를 이용한 백준 문제이다.

 

도시들과 버스가 나오는데

 

도시를 정점으로 보고, 버스의 경로가 간선이라고 보고 문제를 풀면 된다.

 

입력값으로 버스의 시작 도시와 도착 도시, 걸리는 시간이 나오는데

 

시작 도시와 도착 도시가 같은 버스가 있음에 주의해서 최솟값을 graph에 입력시키는 것을 생각한다.

 

#include <bits/stdc++.h>
#define INF 1e9

using namespace std;

// n 도시 수, m 버스 수
int n, m;
// 버스 비용 테이블
int graph[101][101];

int main(void) {
    cin >> n;
    cin >> m;
    // graph 값 INF로 초기화
    for (int i = 0; i < 101; i++) {
        fill(graph[i], graph[i] + 101, INF);
    }
    // 자기 자신 비용 0 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) graph[i][j] = 0;
        }
    }
    // a = 시작도시 b = 도착도시 c = 비용
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (graph[a][b] > c) {
            graph[a][b] = c;
        } else continue;
    }
    // 플로이드 워셜 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
    // 출력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] == INF) {
                cout << "0" << " ";
            } else {
                cout << graph[i][j] << " ";
            }
        }
        cout << '\n';
    }
}

 

 

 

번외 : Warshall 알고리즘

 

 

Warshall 알고리즘은 관계 행렬에서의 연결관계 파악을 빠르고 쉽게하기 위해서 나온 것이다.

 

정점과의 관계가 있으면, 즉 간선이 존재한다면 행렬 값을 1으로 둔다.

 

$$ \mathrm{W}_{0} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} $$

 

가로 줄이 행, 세로 줄이 열이라고 보면

{0, 1}, {1, 1}, {1, 3}, {2, 3} 인 관계가 존재한다. 

유향 그래프로 보다면

0→1,   1→1,    1→3,    2→3

 

4 x 4 행렬이라면 워셜 알고리즘을 4번 반복한다.

 

1열의 위치 (p1, p2, ...)와 1행의 위치 (k1, k2, ...)를 찾고 (pi, ki)의 위치를 모두 1로 변경한다.

 

1열의 1의 위치는 두 번째 자리이고, 1행의 1의 위치도 두 번째 자리이다.

그럼 {1, 1} = 1이 된다.

 

$$ \mathrm{W}_{1} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} $$

 

그다음 

2열의 1의 위치는 첫 번째와 두 번째, 2행의 1의 위치는 첫 번째, 두 번째, 세 번째

{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2} = 1이다.

 

$$ \mathrm{W}_{2} = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} $$

 

3열의 1의 위치는 첫 번째와 두 번째, 3행의 1의 위치는 네 번째

{0, 3}, {1, 3} = 1이다.

 

$$ \mathrm{W}_{3} = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} $$

 

4열의 1의 위치는 첫 번째와 두 번째, 세 번째, 4행의 1의 위치는 없다.

 

$$ \mathrm{W}_{3} = \mathrm{W}_{4} $$

 

연결관계를 찾은 결과 행렬이 구해진다.