15943. 쌍둥이 섬

Code Battle ([Battle 167] 연휴 마지막 날! 내일을 준비하며 코드배틀! )

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)

시간 내에 제출하지 못해 PASS/FAIL 여부는 알 수 없다. (대회가 있다는 것을 종료 30분 전 발견… ㅜㅜ 아쉽)
원형 Queue를 이용하여 pop_back(), pop_front()만으로 가능한 마을 조합을 뽑아내보는 것이 메인 아이디어.
원형 큐에 각 마을 번호를 넣고, 큐의 양 끝에서 마을을 차례로 뽑아내며 도로를 연결할 경우, 만들어진 도로들은 서로 크로스 되지 않을 것이라고 생각했다.
예제 입력에 대해서는 올바른 출력을 한다.

#include <deque>
#include <iostream>

#define POSSIBLE 1
#define IMPOSSIBLE -1

using namespace std;

int solveTestCase(deque<int> villages1, deque<int> villages2) {
    int i = 0;
    while (!villages1.empty()) {
        if (villages1.front() == villages2.front()) {
            villages1.pop_front();
            villages2.pop_front();
        } else if (villages1.front() == villages2.back()) {
            villages1.pop_front();
            villages2.pop_back();
        } else if (villages1.back() == villages2.front()) {
            villages1.pop_back();
            villages2.pop_front();
        } else if (villages1.back() == villages2.back()) {
            villages1.pop_back();
            villages2.pop_back();
        } else {
            return IMPOSSIBLE;
        }
    }
    return POSSIBLE;
}

void solve() {
    int T;
    int N;
    cin >> T;
    for (int testCaseNo = 1; testCaseNo <= T; testCaseNo++) {
        cin >> N;
        deque<int> villages1(N);
        deque<int> villages2(N);
        for (int n = 0; n < N; n++) {
            cin >> villages1.at(n);
            villages1.at(n)--;
        }
        for (int n = 0; n < N; n++) {
            cin >> villages2.at(n);
            villages2.at(n)--;
        }
        cout << '#' << testCaseNo << ' ' << solveTestCase(villages1, villages2) << '\n';
    }
    return;
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("sample_input.txt", "r", stdin);
    // freopen("sample_output.txt", "w", stdout);
    solve();
    return 0;
}