백준 11403번 : 경로 찾기 [C++]

 

 

 

 

 

Floyd Warshall 알고리즘으로 푸는 문제였다.

 

 

Floyd Warshall 알고리즘은 두 정점간의 거리의 최단거리를 구하는 알고리즘이다.

거쳐가는 정점을 기준으로 두 정점이 각각 연결되어있다면 두정점은 연결된 상태라고 보는 것이 바탕이다.

 

i - k - j 일때,

k를 기준으로 for문을 돌리면서 i - k - j 거리를 i - j 거리로 정의하는데

"min( i - j 거리 ,  i - k - j 거리 )" 를 반복한다.

 

 

 

 

#include <iostream>
#include <queue>
//#include <cstring> //memset
#include <algorithm>
using namespace std;

const int MAX = 100;

typedef struct {
	int y, x;
}dir;

int N; 
int graph[MAX][MAX];

void floyd(void) {	
	
	// i -> j 로 가는 길이 없어도
	// k를 거쳐서 갈 수 있으면 갈 수 있다고 여긴다.
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (graph[i][k] && graph[k][j])	// k : 거쳐가는 점
					graph[i][j] = 1;
			}
		}
	}
}

int main(void) {

	cin >> N;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> graph[i][j];
		}
	}
	
	floyd();

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << graph[i][j] << " ";
		}
		cout << endl;
	}


	return 0;
}