codeforces #581 div2 C - Anna, Svyatoslav and Maps ( 플로이드 )

https://codeforces.com/contest/1204/problem/C

 

루프가 없는 단방향 그래프에 대해, 임의의 경로를 입력으로 주고, 그 입력의 처음과 끝은 그대로이지만 경로는 똑같을 수 밖에 없는 정점의 배열을 출력하는 문제. (물론 그 배열의 크기는 최소가 되도록.)

 

위와 같은 그래프와 입력이 1 2 3 4 1 2 3 4 일떄 출력은 1 2 4 2 4 이다.

 

1 3 4 2 4가 안되는 이유는 3번 정점을 방문하면 입력한 경로에서 벗어나기 때문이다.

 

풀이)

1. 첫번째 정점과 마지막 정점은 항상 출력해야 한다.

 그리고 int arr[]에 입력 경로가 담겨있고, vector<pair<int,int>> ans에 출력할 정답을 담는다고 하자. (pair<int,int>엔 정점번호, 입력배열에서의 인덱스) 여기서 인덱스를 저장하는 것은 경로상의 정점 거리를 구해야 하기 때문이다.

2. 일단 arr[0]을 ans 벡터에 넣는다. 그리고 arr[1]부터 arr[m-2]까지 순회하면서 ans에 저장된 마지막 정점과 현재 탐색하는 정점의 다음번 정점(i+1번째)간의 그래프 상 거리(dist1)와 경로상의 거리(dist2)를 비교해서 dist1<dist2라면 ans벡터에 i번째 정점을 넣어주면 된다.

3. arr[m-1]도 넣어준다(마지막 정점)

 

코드로 짜보면

for( int i = 1 ; i <= 경로길이-2 ; i++)

  if( dist1 < dist2 ) ans.push_back( { arr[i], i } );

 

코드와 위의 예시를 섞어 다시 설명하자면

i가 1일 때, 지금 탐색하는 정점은 '2'이고 다음 정점은 '3'이다. ( ans: 1 )

'1'~'3'까지 그래프 거리 = 1  / '1'~'3'까지 경로 상 거리 = 2

지금 탐색하는 정점 '2'를 경로에서 지나치지 않는다면 경로에서 이탈하게 된다.

그러므로 지금 탐색하는 정점 '2' 은 반드시 경로에 포함돼야 한다!

 

i가 2일 때, 지금 탐색하는 정점은 '3'이고 다음 정점은 '4'이다. ( ans: 1 2 )

'2'~'4'까지 그래프 거리 = 2 / '2'~'4'까지 경로 상 거리 = 2

지금 탐색하는 정점 '3'을 경로에서 지나치지 않아도 입력 경로에서 이탈하지 않는다.

따라서 지금 탐색하는 정점 '3'은 경로에 포함될 필요가 없다.

 

가능한 경로 중 가장 짧은 것을 구하는 것이므로 반드시 경로에 포함돼야 하는 정점들만 ans에 넣어주면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int, int> P;
const int MAX = 101;
const int INF = 1e9;
 
int main() {
	int dist[MAX][MAX];
	int n,m, arr[1000001]; cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%1d", &dist[i][j]);
			if (dist[i][j] == 0)
				dist[i][j] = INF;
			if (i == j) dist[i][j] = 0;
		}	
	}
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> arr[i];
 
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
 
	vector<P> ans;
	ans.push_back({ arr[0],0 });
	for (int i = 1; i <= m-2; i++)
		if (dist[ans.back().first][arr[i+1]] < i+1 - ans.back().second )
			ans.push_back({ arr[i],i });
 
	ans.push_back({ arr[m - 1], m - 1 });
 
	cout << ans.size() << '\n';
	for (P p : ans)
		cout << p.first << " ";
}

 

+)

문제 자체가 이해하기 힘들었다. 결국 못풀고 editorial 봤다.