(C++) 백준 1956 : 운동

 그래프에서 탐색 알고리즘을 이용하여 사이클을 찾는 문제입니다. 처음 이 문제를 봤을 때는 다익스트라로 풀 생각을 하다가 바로 플로이드 워셜-알고리즘(Floyd-Warshall Algorithm)이 생각났습니다. 그리고 조금 생각해 봤더니 워셜 알고리즘을 사용하면 바로 풀리겠다는 확신이 생겼습니다. 사이클은 모든 노드가 시작점이 될 수 있기 때문에 모든 노드에 대해 탐색을 진행해야 합니다. 이러한 점에서 모든 노드에 대해 탐색을 진행하는 워셜 알고리즘을 쓰면 매우 간단히 구할 수 있겠다고 생각했습니다.

 

문제풀이

 이 문제는 정말 플로이드 워셜-알고리즘을 한번만 사용하면 풀리는 문제입니다. 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘입니다. 모든 노드에 대해 각각 n번째 노드를 거쳐서 다른 노드로 가는경우와 기존의 경우를 비교해서 더 작은값으로 갱신해 나가는 방식으로 모든 최단거리를 구합니다. 플로이드 워셜 알고리즘은 다음과 같습니다.   

void Warshall()
{
	for (int through = 1; through <= V; through++)
	{
		for (int from = 1; from <= V; from++)
		{
			if (from == through) continue;
			for (int to = 1; to <= V; to++)
			{
				if (graph[from][through] == INF || graph[through][to] == INF)
					continue;
				if (graph[from][to] > graph[from][through] + graph[through][to])
					graph[from][to] = graph[from][through] + graph[through][to];
			}
		}
	}
}

기존의 최단거리 알고리즘의 경우에는 from과 to가 같은경우 continue해서 원레 노드를 다시 방문하는 경우를 제외합니다(굳이 다시 방문하지 않아도 되는 경우이기 때문). 하지만 이 문제에서는 사이클을 찾아야함으로 다시 돌아오는 경우를 포함해서 워셜 알고리즘을 적용시켜야 합니다. 그래서 from과 through가 같은경우(시작노드와 거쳐가는 노드가 같은경우)는 볼 필요가 없으니 제외하고 갱신해 나가면 사이클을 포함한 모든 최단거리를 구할 수 있게 됩니다. 이러한 최단거리중 시작과 끝이 같은 사이클 graph[i][i](1<=i<=V) 중 가장 작은 값이 이 문제의 답이 됩니다.

 

전체 코드입니다.

#include<iostream>
#include<climits>
#define INF INT_MAX

int V, E;
int graph[401][401];

void Warshall()
{
	for (int through = 1; through <= V; through++)
	{
		for (int from = 1; from <= V; from++)
		{
			if (from == through) continue;
			for (int to = 1; to <= V; to++)
			{
				if (graph[from][through] == INF || graph[through][to] == INF)
					continue;
				if (graph[from][to] > graph[from][through] + graph[through][to])
					graph[from][to] = graph[from][through] + graph[through][to];
			}
		}
	}
}


int main() {
	int a, b, c,result=INF;
	std::cin >> V >> E;
	for (int i = 1; i <= V; i++)
		for (int k = 1; k <= V; k++)
			graph[i][k] = INF;
	while (E--)
	{
		std::cin >> a >> b >> c;
		graph[a][b] = c;
	}
	Warshall();
	for (int i = 1; i <= V; i++)
		result = graph[i][i] < result ? graph[i][i] : result;
	if (result == INF)
		std::cout << -1;
	else
		std::cout << result;


}