C++ 11403(경로 찾기)

#include <iostream>
#define INF 987654321

using namespace std;

int arr[101][101];

int main(void)
{
	int a=0;
	
	cin>>a;
	
	for(int i=1; i<=a; i++)
	{
		for(int j=1; j<=a; j++)
		{		
			cin>>arr[i][j];
			if(arr[i][j]==0)
			{
				arr[i][j]=INF;
			}
		}
	}
	
	for(int i=1; i<=a; i++)
	{
		for(int j=1; j<=a; j++)
		{
			for(int k=1; k<=a; k++)
			{
				if(arr[j][i]+arr[i][k]<arr[j][k])
				{
					arr[j][k]=arr[j][i]+arr[i][k];
				}
			}
		}
	}
	
	for(int i=1; i<=a; i++)
	{
		for(int j=1; j<=a; j++)
		{
			if(arr[i][j]==INF)
			{
				cout<<0<<" ";
			}
			else
			{
				cout<<1<<" ";
			}
			
		}
		cout<<endl;
	}
	
	return 0;
}

이 문제는 경로가 있으면 1을 출력하고 없으면 0을 출력하는 문제이다.

나는 플로이드 워샬 알고리즘을 이용하여 해결하였다.

 

일단 처음에 모든 경로를 INF로 초기화해준다.

그리고 도시마다 경유 가능한 경로를 찾는다.

for(int i=1; i<=a; i++)
	{
		for(int j=1; j<=a; j++)
		{
			for(int k=1; k<=a; k++)
			{
				if(arr[j][i]+arr[i][k]<arr[j][k])
				{
					arr[j][k]=arr[j][i]+arr[i][k];
				}
			}
		}
	}

이 부분은 첫 번째 for문이 경유하는 도시를 의미한다. 첫 번째 i가 1이면 1이라는 도시를 모든 도시가 경유하여 값을 재설정한다. i가 2라면 2라는 도시를 경유하여 경로의 값을 갱신한다. 이렇게 1~a까지 수행하면 각 도시 간의 최단거리를 알 수 있다.

 

만약 INF가 그대로 출력되면 경로가 없는 걸로 판단하고 0으로 출력하고

INF말고 다른 값이 출력되면 경로가 있는 걸로 판단하고 1을 출력한다.

 

이 문제는 푸는 방법이 다양하게 존재할 것으로 추측된다. 다양한 방법으로 시도하고 해결해 보는 것도 나쁘지 않아 보인다.