[백준 11403번 / C++/ 플로이드-와샬] 경로 찾기

플로이드-와샬 문제이다. 

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

---

플로이드 와샬 알고리즘을 모르시는 분은 위의 링크에 들어가서 개념을 숙지하고 오길 추천한다. 

 

#접근 방법 

 

노드 1에서 노드 3으로 연결된 길이 있는지 물어봤다면?

 

노드 1에서 노드 2를 거쳤다가 노드 3으로 가는 길이 있는지.

노드 1에서 노드 4를 거쳤다가 노드 3으로 가는 길이 있는지. 

 

이러한 방식으로 확인해보면서 그래프 값을 갱신해주는 것이다. 

 

#include <iostream>
using namespace std; 
int g[101][101]; 
int main() {
	int n; cin >> n; 
	for(int i=0; i<n; i++){
		for (int j = 0; j < n; j++) {
			cin >> g[i][j]; 
		}
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (g[i][k] && g[k][j]) {
					g[i][j] = 1; 
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << g[i][j] << " ";
		}cout << endl; 
	}

}

 

11403번: 경로 찾기