/<> 백준 11403번 : 경로 찾기 (C언어)

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

 

 

임의의 노선 (u, v)가 0일 경우, 경유할 수 있는 노선이 (u, a), (a, b), (b, v) 처럼 존재한다면 u에서 v로 갈 수 있다는 뜻이므로 출력은 1로 합니다. 이 문제는 플로이드-워셜(Floyd-Warshall) 알고리즘을 사용하면 됩니다.

 

플로이드-워셜 알고리즘은 모든 정점 사이의 최단 거리를 구하는 알고리즘입니다. 이 문제는 단순히 갈 수 있냐 없냐 만을 판단하므로, 그냥 출력값을 1로 변경해주면 됩니다.

 

<코드>

#include <stdio.h>

int n;
int graph[100][100];

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

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

	floyd_warshall();

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) printf("%d ", graph[i][j]);
		printf("\n");
	}
	return 0;
}

 

 

최단거리를 구하는 본래의 플로이드-워셜 알고리즘과의 차이점은 다음과 같습니다. 위의 문제에서 노선이 0인 경우에 값을 아주 큰 값(inf)을 부여하고 연산을 진행합니다. 그래서 값의 크기를 비교한 후 변경할 수 있습니다.

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