[백준 11403] 경로 찾기

문제출처: https://www.acmicpc.net/problem/11403

풀이

플로이드 와샬 알고리즘은 매우 직관적이고 쉬운 알고리즘으로써, 이 문제에 적용할 수 있습니다.

직관적으로 생각해보면, a=b, b=c 일때 a=c라는 삼단논법의 논리를 이용하자면,

출발하는길->거치는길이 있고, 거치는길에서 도착하는 길이 있으면, 출발하는길->도착하는길이 존재할 수 있습니다. 따라서 이 논리를 플로이드와샬 구현에 그대로 대입하면됩니다.

코드

#include<iostream>
using namespace std;
int map[100][100];
int n;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	//i=거치는길,j=출발,k=도착
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				//출발->거치는길이 있고, 거치는길->도착하는길이있으면
				if (map[j][i] && map[i][k])
					//출발->도착하는길이있다.
					map[j][k] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << map[i][j] << " ";
		}cout << endl;
	}
}

결과