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

문제 설명

노원구에는 마을 $n + 1$개와 방향이 있는 도로 $2n - 1$개가 있다.

노원구에 있는 도로는 다음 두 종류가 있다.

• 도로 $n - 1$ 개는 $1 \le i \le n - 1$을 만족하는 모든 $i$에 대해서 마을 $i$에서 마을 $i + 1$로 연결되어 있다.
• 도로 $n$개는 수열 $a_1, ..., a_n$ 으로 제시된다. $1 \le i \le n$을 만족하는 모든 $i$에 대해서 만약 $a_i = 0$이면 이 도로는 마을 $i$에서 마을 $n + 1$으로 연결한다. $a_i = 1$이면 마을 $n + 1$에서 마을 $i$로 연결한다.

동환이는 이번주에 노원구를 택시로 돌아볼 생각이다. 지루한 여행이 되지 않기 위해 모든 마을을 정확히 한번만 방문하려고 한다. 동환이는 아무 마을에서 출발하거나 도착해도 상관 없다. 동환이가 계획을 짜는 것을 도와주자.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 20)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 정수 $n (1 \le n \le 10^4)$ 가 주어진다. 이때 마을의 개수는 $n + 1$이다.

각 테스트 케이스의 두번째 줄에는 $n$개의 정수 $a_1, a_2, ..., a_n (0 \le a_i \le 1)$이 주어진다. 만약 $a_i = 0$인 경우 도로가 마을 $i$에서 마을 $n + 1$으로 연결되어있다는 뜻이고, $a_i = 1$인 경우 도로가 마을 $n + 1$에서 마을 $i$로 연결되어있다는 뜻이다.

Output
각 테스트케이스마다 한 줄에 정수 $n + 1$개를 출력한다. $i$번째 숫자는 동환이가 $i$번째에 방문한 마을이다.

Example
input
2
3
0 1 0
3
1 1 0

output
1 4 2 3
4 1 2 3

문제 접근

사용한 알고리즘: 그래프, 구성적 알고리즘
걸린 시간 : 00:12
문제에 주어진 조건을 차근차근 따라가 보면 쉽게 일반화 할 수 있는 경우가 발견된다.

먼저 문제에서 주어진 첫번째 조건인 도로 $n - 1$개에 대한 설명을 그림으로 그려보면 $1$부터 $n$까지 순차적으로 연결하고 있다는 것을 알 수 있다. 즉 마지막 $n + 1$번째 마을을 언제 방문할지를 정하는 것이 문제이다.

만약 $a_1 = 1$ 이면 어떤 상황이 벌어질까? $n + 1$에서 $1$번으로 도로가 연결되어 있다는 뜻이다. 그렇다면 나머지 마을끼리는 도로가 일직선으로 연결되어 있기 때문에 $n + 1$번째 마을을 첫번째로 방문하고 그 다음 $1$부터 $n$까지 마을을 방문하면 된다.

만약 $a_{n} = 0$ 이면 어떤 상황이 벌어질까? $n$에서 $n + 1$으로 가는 도로가 연결되어 있다는 뜻이다. $1$부터 $n$까지 마을은 이미 일직선으로 연결되어 있기 때문에 맨 마지막에 $n + 1$번째 마을을 방문하면 된다.

마지막으로 위의 두 경우를 모두 만족하지 않는 나머지 경우에는 어떤 일이 일어날까? $0$ 과 $1$이 연속적으로 나타나면 무조건 여행할 수 있는 경우가 생긴다. $1$번째 마을부터 시작해서 여행을 시작하는데 여행을 시작하다가 $k$번째 마을에서 $n + 1$ 마을로 가는 도로를 발견하면 바로 $n + 1$로 이동하고, $k + 1$번째 마을로 가는 도로를 발견하면 바로 $k + 1$로 이동하면 된다. 여기서 $0$과 $1$이 연속적으로 나타나지 않으면 건너뛰는 마을이 생길 수 있기 때문에 반드시 연속되어야 한다.

여기서 의문점이 하나 생길 수 있다. 그렇다면 답이 없는 경우도 있는거 아닌가요? 하지만 그럴일은 절대로 없다. 마지막 나머지 경우에는 반드시 $a_1 = 0$ 이고, $a_{n} = 1$ 여야 한다. 이때 그 사이에 있는 수는 아무렇게나 해도 무조건 $0$ 과 $1$이 무조건 붙어 있는 경우가 최소 1개 이상 나올 수 있다. 증명은 구성적 알고리즘의 특징답게 그냥 예시를 만들어 봐야 한다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        int arr[n];
        for(int i = 0; i < n; i++) cin >> arr[i];
        if(arr[0]){
            cout << n + 1 << " ";
            for(int i = 1; i <= n; i++) cout << i << " ";
        }else if(!arr[n - 1]){
            for(int i = 1; i <= n + 1; i++) cout << i << " ";
        }else{
            bool flag = true;
            for(int i = 0; i < n - 1; i++){
                cout << i + 1 << " ";
                if(!arr[i] && arr[i + 1] && flag){
                    cout << n + 1 << " ";
                    flag = false;
                }
            }
            cout << n << " ";
        }
        cout << "\n";
    }
    return 0;
}