[백준 11404] 플로이드

문제 링크 => 11404번: 플로이드 (acmicpc.net)

11404번: 플로이드

 

Floyd-warshall 알고리즘을 이용한 문제이다.

 

문제 풀이순서는 다음과 같다. (d[x][y] = x에서 y까지 이동할 수 있는 최단 경로)

1. d[x][y] 의 값을 미리 세팅한다.

    (1) x = y 일 경우 : d[x][y] = 0 (자기 자신으로 가는 경우는 0)

    (2) x ≠ y 일 경우 : d[x][y] = INF (이동할 수 없는 경우를 INF 으로 마킹)

 

2. 인풋으로 주어진 x, y, distance 에 대해서 세팅한다.

     d[x][y] = distance

 

3. 모든 세팅이 끝났으므로 3중 for문을 이용하여 다음과 같이 d[x][y] 의 값을 최소로 업데이트 해준다.

     

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

 

k값을 1부터 시작하여 n까지 3중 for문을 돌린다면 해결할 수 있다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define INF 100000000

using namespace std;

int d[101][101];

int min(int x, int y) {
	return x < y ? x : y;
}

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

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int x, y, distance;
		scanf("%d %d %d", &x, &y, &distance);
		d[x][y] = min(distance, d[x][y]);
	}

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

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

	return 0;
}