백준 / BOJ / 11403 경로찾기 C++

www.acmicpc.net/problem/11403

11403번: 경로 찾기

지난 주에 교내 알고리즘 대회에서 탈탈 털려서 (구현은 대체적으로 해냈지만 테스트 케이스를 통과 못해서 상은 받지 못했다....) 기본 문제를 하나 풀어보았습니다.

간단한 그래프 문제입니다. 방향 그래프에서 모든 정점에서 모든 정점으로 가는 경로의 유무 (최단 경로X) 만 판단하면 되는 간단한 문제입니다. 최단 경로가 아닌 경로의 유무만 알면되기에 다양한 방법이 있지만, 플로이드 와샬 알고리즘을 이용하여 풀었습니다.

 

플로이드 와샬 알고리즘이란 가중그래프에서 모든 정점에서 모든 정점으로 가는 최단거리를 계산할 때 주로 사용합니다. 유명한 알고리즘이라 간단히 설명하면, 정점 i, j에 대해 i -> j 로 가는 경로의 가중치 w를 arr[i][j]=w, 경로가 없다면 arr[i][j] = inf 로 설정하여 다른 중간 정점 k를 이용해 i -> k -> j로 가는 경로가 존재하고, 이 거쳐가는 경로가 arr[i][j] 보다 작은 값이라면 arr[i][j] = arr[i][k] + arr[k][j] 로 업데이트 하는 것입니다. 

 

이렇게 하여 i에서 j로 가는 최단 경로를 구할 수 있습니다. 이것이 가능한 이유는 i -> k -> j 로 가는 모든 경로에 대해 조사하고 작은 값을 계속 업데이트하기 때문에 가능합니다. 

 

단순히 모든 시작 정점, 모든 끝 정점, 모든 중간 정점에 대해 조사하기 때문에 복잡도는 O(n^3) 입니다. (n : 정점 개수)

 

위 문제에서는 최단 경로는 구할 필요 없이 경로의 유무만 판단하면 되므로 플로이드 와샬 알고리즘을 적용하였을 때 arr[i][j] != inf 면 경로가 존재하는 것으로 생각할 수 있습니다. 

n<=100 이므로 시간도 넉넉하고 해서 그냥 플로이드 와샬 복습 겸 풀었습니다.

inf를 987654321로 잡았는데, 문제의 가중치가 모두 1이라 생각할 수 있고, 100개의 정점이 모두 양방향으로 연결되어있다하더라도, 총 간선의 개수는 100 * 99개이므로 inf를 넘지못합니다. (100C2 * 2 = 100 * 99)

 

#include<iostream>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int main()
{
	int n;
	int inf = 987654321;
	cin >> n;
	int** arr = (int**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++)
		arr[i] = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0)
				arr[i][j] = inf;
		}

	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (arr[i][j] > arr[i][k] + arr[k][j])
					arr[i][j] = arr[i][k] + arr[k][j];
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] != inf)
				cout << 1 << ' ';
			else
				cout << 0 << ' ';
		}
		cout << '\n';
	}
}