#738 (Div.2) C - Mocha and Hiking

문제 링크 => Problem - C - Codeforces

Problem - C - Codeforces

---

그래프를 이용한 문제이다.

 

주어진 조건으로 얻은 그래프를 통해서 무조건 한번만 마을을 방문하여 모든 마을을 방문할 수 있는지를 묻는 문제이다.

 

문제에서 주어진 조건을 단순하게 요약하면 다음과 같다.

 

n(1~10000, 정수)값이 주어질 때,

 

(1) 1 번째 마을에서 2 번째 마을로 가는 도로 존재 

     2 번째 마을에서 3 번째 마을로 가는 도로 존재 

     ...

     (n - 1) 번째 마을에서 n 번째 마을로 가는 도로 존재 

 

(2) ai = 0 ) i 번째 마을에서 (n + 1) 번째 마을로 가는 도로 존재 

     ai = 1 ) (n + 1) 번째 마을에서 i 번째 마을로 가는 도로 존재

 

확실한 것은 (1) 조건만으로 1 번째 마을에서 n 번째 마을로 한번씩 방문이 가능하다는 것이다.

 

문제는 (n + 1) 번째 마을인데 다음과 같은 3가지 Case를 통해서 방문이 가능하다.

 

 

Case 1) (n + 1) 번째 마을이 1로 연결된 경우

 

Case 2) n 번째 마을이 (n + 1) 번째 마을로 연결된 경우

 

Case 3) 1 <= i <= (n - 1) 를 만족하는 i 에 대하여 i 번째 마을이 (n + 1) 번째 마을로 연결된 경우와 (n + 1) 번째 마을이 (i + 1) 번째 마을로 동시에 연결된 경우

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

void test() {

	int n;
	cin >> n;

	map<pair<int, int>, int> m;

	for (int i = 1; i <= n - 1; i++) {
		m[{i, i + 1}] = 1;
	}
	
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		if (x == 0) m[{i, n + 1}] = 1;
		else m[{n + 1, i}] = 1;
	}

	for (int i = 0; i <= n; i++) {
		if (i == 0) {
			if (m[{n + 1, 1}]) {
				cout << n + 1 << " ";
				for (int j = 1; j <= n; j++) cout << j << " ";
				cout << endl;
				return;
			}
		}
		else if (i == n) {
			if (m[{n, n + 1}]) {
				for (int j = 1; j <= n + 1; j++) cout << j << " ";
				cout << endl;
				return;
			}
		}
		else {
			if (m[{i, n + 1}] && m[{n + 1, i + 1}]) {
				for (int j = 1; j <= i; j++) {
					cout << j << " ";
				}
				cout << n + 1 << " ";
				for (int j = i + 1; j <= n; j++) cout << j << " ";
				cout << endl;
				return;
			}
		}
	}

	cout << -1 << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) test();

	return 0;
}