[백준] 11404번 : 플로이드 [C/C++]

#문제

11404번: 플로이드

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

11404번: 플로이드

 

---

#접근방법

최단거리 알고리즘 중 모든정점에서 모든정점으로 가는 최단거리를 구하는 플로이드 워셜 알고리즘을 사용해야한다.

 

이 알고리즘은 O(n^3)이라는 시간복잡도가 걸린다.

반응형

---

#풀이

#include <stdio.h>
#define INF 987654321

int arr[105][105];

int main(){
    int n,m;
    int a,b,c;

    scanf("%d",&n);
    scanf("%d",&m);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            arr[i][j] = INF;

    for(int i=1;i<=n;i++)
        arr[i][i] = 0;

    for(int i=0;i<m;i++){
        scanf("%d %d %d",&a,&b,&c);

        if(arr[a][b]>c)
            arr[a][b] = c;
    }

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

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


    return 0;
}

 

이 문제는 위에서 말한 것 처럼 플로이드 워셜 알고리즘을 사용하는게 적절하다. n<=100이므로 O(100^3)이라는 시간복잡도는 시간안에 돌아간다.

 

n,m을 입력받고 arr배열을 모두 무한대로 초기화해준다. 왜냐하면 최소거리를 구하는 조건문을 쓸 때 편리하기 때문이다. 그리고 arr[i][i]와 같이 자기자신은 0으로 초기화 해준다.

 

a,b,c를 m만큼 입력받을 때 같은 a,b값이 여러번 나올 수 있으므로 if(arr[a][b]>c)일 때 arr[a][b] = c를 입력받도록 조건문을 걸어준다.

 

배열을 다 입력받았으면 3중첩 반복문을 돌면서 arr[i][j] > arr[i][k] + arr[k][j]일 때 arr[i][j]의 값을 바꾸어준다. 이 반복문과 조건문이 플로이드 워셜 알고리즘의 핵심이다.

 

조건문에서 arr[i][j]의 의미는 i에서 j로 가는 비용이라는 뜻이다.

그리고 arr[i][k] + arr[k][j]의 의미는 i에서 k로 가는 비용과 k에서 j로가는 비용의 합이다. i에서 k를 거쳐서 j로 가는 비용이 원래 입력받았던 i에서 j로 가는 비용보다 작을 수 있으므로 이 때는 arr[i][j]값을 arr[i][k] + arr[k][j]로 바꿔준다.

 

그리고 arr배열을 출력하면되는데 이 때, 무한대로 초기화한 값을 0으로 출력을 하면 정답이다.

---

#성능

---

#정리

최단거리 알고리즘 중 모든정점에서 모든정점으로 가는 최단거리를 구하는 플로이드 워셜 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제였다.