[백준 11403] 경로 찾기

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

---

해설

이번 문제도 11403번 플로이드 ( 참고 : https://far-simple.tistory.com/8 ) 문제와 마찬가지로 플로이드 와샬 알고리즘을 사용 해 푸는 문제입니다.

11403번 풀이에 플로이드에 관한 설명을 해놨으니 읽어보고 오시길 바라겠습니다.

 

문제에서 인접행렬이라고 써져있어서 뭐지? 싶을수도 있겠지만 그냥 N*N으로 출력하면 됩니다.

플로이드 점화식으로 중간에 임의의 점 k를 껴서 i->k 와 k-> j 에 길이 있다면 arr[i][j]를 1로 초기화 시켜주시면 됩니다.

 

 

˙˙˙

 

소스 코드

 

#include <iostream>
using namespace std;
int arr[101][101];
int main(){
	int n; cin >> n;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cin >> arr[i][j];
	
    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;
	
    for(int i=0; i<n; i++){
		for(int j=0; j<n; j++)
			cout << arr[i][j] << ' ';
		cout << '\n';
	}
}