[백준/C++] 가운데에서 만나기 (No. 21940)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 풀 때, 어떤 답을 원하는지 정확히 알기 힘들었다...

 

일단 왕복시간이 a도시에서 b도시를 방문하고 a도시로 돌아오는 경우로만 정의되어있어 아무 값이나 사용하면 되는지, 최솟값을 사용해야하는지 명확하지 않았다.

 

친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다. 라는 지문이 있는데 이 의미가

 

먼저 친구들이 i도시를 왕복하는 시간들을 각각 구한다.

그 다음 그 왕복 시간 중 최대값을 구한다.

이제 1~N번 도시까지 구한 최대값을 비교하고 그 중 최솟값을 찾아 최솟값인 도시의 번호를 출력한다.

이때, i번 도시에 살고있는 사람은 i번 도시에 왕복하는 비용을 계산하지 않는다.

라는 의미다;;

 

그래서 예제의 입력과 출력을 보고 의미 파악을 겨우 할 수 있었다..

 

푸는 방법은 간단하다 모든 도시에 대해 비용을 계산해야 하므로 플로이드 와샬 알고리즘으로 a도시에서 b도시로 가는 최소 비용들을 전부 구하면 된다.

 

이후 친구들이 i번째 도시에 방문하는 경우의 최대 왕복시간을 계산한다.

그렇게 N개의 도시에 대해 최대 왕복 시간이 계산됐다면, 도시들의 최대 왕복시간이 가장 작은 시간을 찾는다.

 

이제 그 시간만큼 왕복 시간이 걸리는 도시들이 정답이므로 도시들의 번호를 출력하면 된다.

 

 

 

[아이디어 정리]

1. 플로이드 와샬 알고리즘을 이용해 각 도시에 방문하는 최소 비용을 구한다.
2. N개의 도시에 대해 i번 도시에 친구들이 왕복하는 시간을 계산한다.
3. 계산된 시간 중 최대 값이 i번 도시의 왕복시간의 최대값이다.
4. 이제 N개의 도시에 대해 왕복시간의 최대값이 가장 작은 시간을 찾는다.
5. 왕복시간의 최대값이 가장 작은 시간과 똑같은 도시의 번호를 출력한다.

 

 

Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;

int INF = 987654321;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N,M,K;
	cin >> N>>M;
	vector<vector<int>> graph(N + 1, vector<int>(N + 1, INF));
	int a, b, c;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		graph[a][b] = c;
	}
	cin >> K;
	vector<int> v(K);
	for (int i = 0; i < K; i++) {
		cin >> v[i];
		graph[v[i]][v[i]] = 0;
	}
	for (int k=1; k<=N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++) 
			{
				if (graph[i][k] != INF && graph[k][j] != INF)
				{
					graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
				}
			}	
		}
	}
	int rc, flag, ans, tmp;
	ans = INF;
	vector<int> calc(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		rc = 0;
		flag = true;
		for (int k = 0; k < K; k++)
		{
				if (i!=v[k])
				{
				tmp = 0;
				tmp += graph[i][v[k]];
				tmp += graph[v[k]][i];
				if (graph[v[k]][i]== INF)
				{
					flag = false;
					break;
				}
				if (graph[i][v[k]]== INF)
				{
					flag = false;
					break;
				}
				if (flag) {
					rc = max(rc, tmp);
				}
			}
		}
		calc[i] = rc;
		ans = min(ans, rc);
	}
	for (int i = 1; i <= N; i++) {
		if (calc[i]==ans)
		{
			cout<<i<<" ";
		}
	}
	return 0;
}

---

 

문제는 어렵지 않았는데, 조건이 빠져있고 명확하지 않아서 헷갈렸던 문제다

 

풀었지만 너무 찜찜하네...

 

 

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