/<> 백준 11404번 : 플로이드 (C언어)

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

 

 

그래프 문제 중 플로이드-워셜(Floyd-Warshall) 알고리즘을 사용하는 문제입니다. 플로이드-워셜 알고리즘은 한 노드가 다른 노드에게 도달하는 데 걸리는 최소 비용(시간)을 모두 구하는 알고리즘입니다.

 

그래프 탐색 이론에는 크게 데이크스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall) 이렇게 세 가지로 나뉩니다(학교에서 배운 기준). 데이크스트라의 단점은 비용이 음수일 땐 사용할 수 없고, 벨만-포드보다 플로이드-워셜이 좀 더 효율적입니다. 사실 세 알고리즘 모두 시간 복잡도가 O(n^3)인데, 코드 리딩의 과정에서 차이가 납니다. 간단한 그래프를 그리고 각 세 종류의 알고리즘을 따라 최소 비용을 직접 손으로 쓰면서 모두 구해보면 훨씬 이해가 빠릅니다(수업 복습할 때 이렇게 공부했습니다).

 

 

1. 노드와 노드를 잇는 간선의 비용 정보를 저장하는 배열을 생성합니다.

 

2. 문제에서 같은 간선이 중복으로 입력될 수 있다는 정보가 있으므로, 비용을 입력받을 때 겹치는 부분은 최소 비용으로 저장합니다.

 

3. 플로이드-워셜 알고리즘을 통해 출발 노드의 모든 목적지의 최소 비용을 배열에 새로 저장합니다.

 

4. 배열을 출력합니다. 3단계를 통해 출발점에서 도착점까지 모두 최소 비용으로 저장되어 있습니다.

 

 

<코드>

#include <stdio.h>
#define inf 987654321

int n, m;
int cost[101][101] = {0, };

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

int main() {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                        if(i == j) cost[i][j] = 0;
                        else cost[i][j] = inf;
                }
        }

        for(int i = 0; i < m; i++) {
                int u, v, c;
                scanf("%d %d %d", &u, &v, &c);
                if(!cost[u][v]) cost[u][v] = c;
                else if(cost[u][v] > c) cost[u][v] = c;
        }

        floyd_warshall();

        for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                        if(cost[i][j] == inf || i == j) printf("0 ");
                        else printf("%d ", cost[i][j]);
                }
                printf("\n");
        }
        return 0;
}

 

 

저번 학기 때 배운 자료구조 내용들이 요즘 백준을 풀면서 많이 보입니다. 진작에 학기 중에도 백준을 풀며 복습을 했으면 어떨까 싶네요. 이번 2학기때도 알고리즘 수업이 있으니, 백준을 통해 복습을 착실히 해야겠습니다.