경로찾기 | 백준 11403번

#include <iostream>
using namespace std;

int main() {
	int n;
	int graph[100][100];

	cin>>n;
	
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cin>>graph[i][j];

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


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

	return 0;
}

이 문제는 모든 점에서 갈 수 있는 경로를 찾는 문제이다.
이러한 문제는 플로이드-워셜 알고리즘을 사용한다. 말이야 거창하지만, for 문을 i, j, k에 대하여 각각 반복함으로써, 모든 점에서 가능한 경우를 확인하는 것이다.
여기서 중요한 점은 i, j에 대한 모든 점을 확인할 때, 중간 점으로 사용하는 k의 for 문이 가장 바깥에 위치해야 한다. (코드 참고)
이런 과정을 거치면 우리가 가진 graph 배열은 모든 점에서의 경로를 갖게된다.

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest