[BOJ] 백준 11404번 플로이드

백준 11404번 문제 링크 및 접근 방법

플로이드 문제 링크

11404번: 플로이드

백준 사이트 11404번 문제인 플로이드 문제입니다. 플로이드-와샬 알고리즘을 이용해서 풀 수 있습니다.

 

플로이드-와샬 알고리즘(Floyd Warshall)

간단하게 플로이드-와샬 알고리즘에 대해 설명하겠습니다. a 지점에서 c 지점으로 갈 때 한 지점을 거쳐서 더 빠르게 갈 수 있다면 그 최단거리를 구하는 알고리즘입니다. 예를 들어서 a->c로 바로 가는 것보다 a->b->c가 빠르다면 a->b->c가 최단거리가 되는 것입니다. 만약 어떤 지점을 거치지 않고 a 지점에서 c 지점으로 바로 가는 것이 최단거리라면 a -> c의 거리를 적용하면 됩니다. 

 

문제 소스 코드

#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

const int INF = 987654321;

int city[102][102];
int n, bus;;

void floyd() {
	// k : 거쳐가는 지점
	for (int k = 1; k <= n; k++) {
		// i : 처음 시작점 
		for (int i = 1; i <= n; i++) {
			// j : 도착지점
			for (int j = 1; j <= n; j++) {
				if (i == j || j == k || k == i) continue;
				if (city[i][j] > city[i][k] + city[k][j]) { 
                // i->j로 가는 것보다 i->k->j가 더 가깝다면 i->j의 최단거리를 i->k->j로 해줌
					city[i][j] = city[i][k] + city[k][j];
				}
			}
		}
	}
}
int main(void) {
	scanf("%d%d", &n, &bus);

	for (int i = 0; i < bus; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (city[a][b] != 0) // 또 다른 값이 들어오면 제일 최소값으로 대입
			city[a][b] = min(city[a][b], c);
		else
			city[a][b] = c;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j && city[i][j] == 0) {
				city[i][j] = INF;
			}
		}
	}

	floyd();

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

}

개발 환경 : Visual Studio 2019