[백준/C++] 미확인 도착지

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 시작점 st에서 도착점 ed로 가는 최단 경로에 임의의 두 점 (m, n)을 잇는 경로가 포함되어 있는지 계산하는 문제다.

 

문제를 해결하는 방법은 여러 방법이 있다.

 

1. Dijikstra 알고리즘으로 두 점 m, n을 잇는 경로를 포함하는지 체크한다.

2. Dijikstra 알고리즘으로 최단경로와 [st -> m -> n -> ed,   st -> n -> m -> ed]의 최단 경로의 길이가 같은지 비교하는 방법이 있다.

 

이 중에서 1번 방법으로 코드를 구현해 문제를 풀었다.

 

Dijikstra 알고리즘과 동일하게 코드를 구현하지만 m, n을 잇는 경로를 포함하는지 체크할 배열을 하나 만든다.

 

이후 st에서 출발해 도착하는 최단경로를 구한다.

이때, 임의의 도착점 c에 도달한 최단경로가 m, n을 잇는 경로를 이용했다면, 배열[c]를 true로 바꾼다.

 

그러면 st -> c -> j 가 최단 경로인 도착점 j는 마찬가지로 m, n 을 잇는 경로를 이용해야 최단경로가 된다.

 

이 과정을 코드로 구현해 도착점 ed에 도착하는 최단경로가 m, n을 잇는 경로를 이용해 도착점 후보가 될 수 있는지를 판단했다.

 

 

​

[아이디어 정리]

1. Dijikstra 알고리즘으로 시작점 st에서 다른 정점 ed에 도착하는 최단경로를 구했다.
2. 최단경로를 구하는 과정에서 조건에서 원하는 두 점을 잇는 경로를 지났는지 판단하고 지났다면 도착점의 후보가 될 수 있다고 배열에 표시했다.
3. 도착점 후보 목록이 주어지면, 배열의 값이 true인지 확인해 오름차순으로 출력다.

 

 

Code

 

 

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



const int INF = 100000000;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int TC;
	cin >> TC;
	for (int tc = 0; tc < TC; tc++) 
	{
		int n, m, t, s,g,h,a,b,d;
		cin >> n >> m >> t;
		vector<int>vCost(n + 1, INF);  // 비용을 저장할 vector
		vector<bool>visited(n +1, false); // 방문한 적이 있는지
		cin >> s >> g >> h;
		vector<vector<pair<int,int>>> graph(n + 1); // 그래프
		vector<bool> visitC(n + 1, false); // 두 경로를 지난 값이 최단경로인지
		pair<int, int> np;
		for (int i = 0; i < m; i++) 
		{
			cin >> a >> b >> d;
			graph[a].push_back(make_pair(b, d));
			graph[b].push_back(make_pair(a, d));
		}
		vCost[s] = 0;
		while (true) 
		{
			int st=0, cost=INF;
			for (int i = 1; i <= n; i++)
			{
				if (!visited[i] && vCost[i] < cost)
				{
					st = i;
					cost = vCost[i];
				}
			}
			if (st == 0) 
			{
				break;
			}
			visited[st] = true;
			for (int i = 0; i < graph[st].size(); i++) 
			{
				np = graph[st][i];
				int temp = cost + np.second;
				bool flag = visitC[st];
				if (np.first == g && st == h)
					flag = true;
				else if (np.first == h && st == g)
					flag = true;
				if (temp< vCost[np.first])
				{
					vCost[np.first] = temp;
					visitC[np.first] = flag;
				}
				else if (temp == vCost[np.first]) 
				{
					if (!visitC[np.first]) 
					{
						visitC[np.first] = flag;
					}
				}
			}

		}
		vector<int> ans;
		int x;
		for (int i = 0; i < t; i++) 
		{
			cin >> x;
			if (visitC[x])
				ans.push_back(x);
		}
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << " ";
		cout << "\n";
	}
	return 0;
}

 

---

이전에 풀었던 Dijikstra 문제와 비슷하지만, 최단경로에 임의의 간선이 포함되어 있는지 확인하는 게 약간 다른 문제였다.

 

9370번: 미확인 도착지