BOJ

[C/C++] 백준 - 11403번 (Floyd Warshall 알고리즘)

JWonK 2021. 6. 25. 15:02
728x90
반응형

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

 

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

www.acmicpc.net

i->j가 연결되어있지 않더라도

i->k->j가 연결되어있다면 연결표시해주면 됨

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX_SIZE 101

int INF = 10000000;

// 자료 배열 초기화
int arr[MAX_SIZE][MAX_SIZE]; 
int ans[MAX_SIZE][MAX_SIZE];
int N;

void floydWarshall() {
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][k] && arr[k][j]) arr[i][j] = 1;
			}
		}
	}
}

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

	floydWarshall();

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

	return 0;
}
728x90
반응형