[백준/C++] 운동

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 도시에서 시작해 다시 돌아오는 사이클이 있는지 확인하고 있다면, 그 중 가장 비용이 적은 사이클을 출력하는 문제다.

 

사이클을 찾기 위해서는 결국 st 에서 st로 돌아오는 최소비용을 구해야 한다.

 

문제는 시작점이 하나만 주어진게 아니라 모든 도시가 시작점이 될 수 있다는 점이다.

 

그러므로 결국 모든 도시에 대해서 시작점으로 돌아오는지 탐색을 해야한다.

 

처음에는 priority queue를 사용한 다익스트라 알고리즘으로 풀려고 했으나, N개의 점에 대해 다익스트라 연산을 하면 시간복잡도가 O(V*Elog(V))가 된다. [(E < V*2) 이므로 log(V)로 표현 가능] 

 

그러면 O(V^3log(V))가 돼 시간초과가 날 수 있다.

 

대신 플로이드 워셜 알고리즘으로 모든 지점을 탐색한다면 O(V^3)의 시간복잡도로 문제를 해결할 수 있다.

 

그러므로 플로이드 워셜 알고리즘을 이용해 i번째 도시에서 i번째 도시로 돌아오는 사이클이 있는지 확인하고 있다면, 최소비용을 갱신해 문제를 풀었다.

 

 

 

​

[아이디어 정리]

1. 플로이드 워셜 알고리즘을 이용해 모든 도시에 대해 최소비용을 계산한다.
2. 계산이 끝났다면, i 도시에서 출발해 i 도시로 돌아오는 사이클 중 가장 비용이 작은 값을 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;

const int INF = 100000000;
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int N, E;
	cin >> N >> E;
	vector<vector<int>>cost(N+1,vector<int>(N+1,INF));
	int a, b, c;
	for (int i = 0; i < E; i++) 
	{
		cin >> a >> b >> c;
		cost[a][b] = c;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j=1; j<=N; j++)
			{
				cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}
	}
	int answer = INF;
	for (int i=1; i<=N; i++)
		answer = min(answer, cost[i][i]);
	if (answer == INF)
		cout << -1;
	else
		cout << answer;
	return 0;
}

 

---

우선순위 큐를 이용한 다익스트라 알고리즘의 시간복잡도에 대해 다시 생각해 볼 수 있는 문제였다.

 

1956번: 운동