백준 Silver 1 경로 찾기

경로 찾기 (백준 Silver 1)

https://www.acmicpc.net/problem/11403

오랜만에 푸는 플로이드 - 워셜 알고리즘 문제이다
일반적인 길찾기 알고리즘은
출발 - 목적지 가 명확하게 정해져 있지만
‘모든 쌍’에 대한 각각의 최단 거리가 필요할 때는
다소 무거운 O(n^3)이더라도
플로이드 - 워셜을 적용하여 푸는것이 정답이다

다만 정점의 거리 사이에 음수 사이클이 없어야 하며
O(n^3)의 시간 복잡도를 가지기에
n의 개수가 지나치게 올라가는 경우엔 권장하지 않음
(그렇기에 n이 1천개가 넘어간다면
플로이드-워셜이 맞을까하는 의심을 가져보자)

플로이드 - 워셜

모든 정점의 쌍(i,j)에 대하여
중간의 경유 정점 ‘k’를 거쳐갔을 때
최단 거리가 갱신되는가
를 판단하는 알고리즘

따라서 기본적으로 갈 수 없는 거리의 길이를
‘무한대’ 등으로 잡아두고

i -> k -> j 의 거리가
i -> j 보다 짧은가 를 계산한 후
갱신하는 방식이다

출 -> 경 -> 목 으로 기억해보자

의사코드로 보자면

dist[i][j] = INF;

for(k)
 for(i)
  for(j)
   if(dist[i][k] + dist[k][j] < dist[i][j])
    dist[i][j] = dist[i][k] + dist[k][j]; // 갱신

적용하는 경우와
‘출발->경유->목적’ 인 순서만 기억한다면
어렵지 않다

풀이 결과

원래는 dfs나 bfs를 적용하여 풀려 하였으나
결국 ‘모든 쌍’에 적용해야 하며
여태까지의 ‘경로’를 저장하며 진행하는 방식으로
구현하는 것보다 플로이드 - 워셜로 거리를 구하고
그 거리가 초기값이 아니라면,
그냥 1을 출력하는 편이 더 간단하다고 판단하였다

제출 코드

#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;

int main()
{
	int n;
	cin >> n;

	const int semiV = INT_MAX / 2;

	vector<vector<int>> results(n, vector<int>(n, semiV));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int t;
			cin >> t;
			if(t == 1)
				results[i][j] = t;
		}
	}

	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (results[i][k] + results[k][j] < results[i][j])
				{
					results[i][j] = results[i][k] + results[k][j];
				}

			}
		}
	}
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (results[i][j] == semiV)
				cout << 0 << ' ';
			else
				cout << 1 << ' ';
		}
		cout << '\n';
	}

}