[백준/C++] 힘세고 강한 아침

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음 이 문제를 풀 때, query가 들어올 때마다 계산을 했다.

그랬더니 시간초과가 나서 반복되는 계산을 줄이도록 문제를 풀었다.

 

N이 100이기 때문에 첫 언어, 중간 언어를 정해 특정 언어로 변환하는데 걸리는 최소 비용을 계산할 수 있기 때문이다.

이 경우 O(N^2 * 최소 비용을 계산하는 시간복잡도) 이므로 문제가 해결될 것이라고 생각했다.

 

처음에 최소 비용을 계산할 때, priority queue를 이용해 탐색하지 않은 언어 중 항상 변환 비용이 가장 낮은 언어가 앞에 오도록 코드를 구현했다.

 

문제는 priority queue에 삽입하는데 O(logn)의 시간복잡도가 걸리기 때문에 시간초과가 또 났다...

 

결국 priority queue를 이용하지 않고 방문한 적이 없는 언어 중, 비용이 가장 낮은 언어를 골라 탐색을 하도록 코드를 구현했다.

 

탐색 과정은 아래 그림과 같다.

이전에 방문한 적 없는 언어 중 가장 비용이 낮은 언어를 골라 변환이 가능한 언어를 갱신하면 된다.

 

이 모든 언어를 탐색했다면, 탐색을 종료하면 된다.

 

​

[아이디어 정리]

1. 특정 언어를 s 변환 중에 거치지 않을 언어를 m, 최종적으로 변환될 언어를 e로 3차원 vector를 만든다.
2. 이후 query의 반복계산을 줄이기 위해 s와 m을 기준으로 변환이 되는 언어들에 대해 모든 최소비용을 계산한다.    (다익스트라 알고리즘 활용)
3. 계산이 끝나면 query에 맞춰 최소 비용을 return한다.

 

 

 

Code

 

 

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


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M, Q;
	//s에서 k빼고 e로
	cin >> N >> M >> Q;
	vector<vector<pair<int,int>>> cost(N+1);
	int b, t, c;
	for (int i = 0; i < M; i++) 
	{
		cin >> b >> t >> c;
		cost[b].push_back(make_pair(t,c));
	}
	vector<vector<vector<int>>> minCost(N+1, vector<vector<int>>(N+1, vector<int>(N+1,10000000))); //st,mid,ed

	pair<int, int> np;
	for (int st = 1; st <= N; st++) 
	{
		for (int mid = 1; mid <= N; mid++) 
		{
			if (mid==st)
			{
				continue;
			}
			vector<bool> visited(N + 1, false);
			int nowNode = st;
			minCost[st][mid][st] = 0;

			while (!visited[nowNode])
			{
				
				visited[nowNode] = true;
				for (int i = 0; i < cost[nowNode].size(); i++) 
				{
					np = cost[nowNode][i];
					if (np.first != mid) 
					{
						int nextCost = minCost[st][mid][nowNode] + np.second;
						if (nextCost<minCost[st][mid][np.first]) 
						{
							minCost[st][mid][np.first] = nextCost;
						}
					}
				}
				int minC = 10000000;
				for (int i = 1; i <= N; i++) 
				{
					if (!visited[i]&& minCost[st][mid][i]<minC)
					{
						minC = minCost[st][mid][i];
						nowNode = i;
					}
				}
			}
		}
	}
	int s, k, e;
	for (int i = 0; i < Q; i++) 
	{
		cin >> s >> k >> e;
		if (minCost[s][k][e] == 10000000) 
		{
			cout << "No\n";
		}
		else 
		{
			cout << minCost[s][k][e] << "\n";
		}
	}

	return 0;
}

 

---

처음에 다음에 탐색을 할 노드를 찾는데 N^2의 시간 복잡도가 걸려서 priority queue를 사용했다.

하지만 오히려 priority queue에 삽입한 후, 정렬되는 과정에서 시간이 오래 걸렸다.

다음부터는 시간복잡도에 대해 잘 생각하고 풀도록 하자...

 

31566번: 힘세고 강한 아침