[백준 17300번] 패턴 풀이

17300번: 패턴

 

N개의 숫자를 입력 받았을 때, 해당 패턴이 허용되면 "YES", 허용되지 않으면 "NO"를 출력하는 문제이다.

패턴의 조건은 다음과 같다.

 

1) 패턴을 나타내는 수열에는 같은 점이 두번 이상 등장하지 않는다.

2) 수열의 인접한 점을 연결해 만든 선분 위에는 아직 등장하지 않은 점이 있을 수 없다.

 

먼저, 이전 입력으로 어떠한 숫자가 주어졌을 때 다음 입력으로 가능한 숫자 목록을 정리해보자.

 

입력이 1~9일 떄 각각 이동 가능한 수

 

현재 숫자 1이 입력되었다면, 다음번에는 직선상에 있는 2, 4, 5, 6, 8에 아무런 제약 없이 도달할 수 있다. 그러나 3의 경우 2가 입력된 적이 있을 때, 7의 경우 4가 입력된 적이 있을 때, 9의 경우 5가 입력된 적이 있을 때에만 도달할 수 있다. 

 

따라서, 1의 입력 뒤에 도달할 수 있는 다음번 수의 목록은 다음과 같이 처리한 결과가 된다.

 

일단 1, 2, 3, 4, 5, 6, 7, 8, 9로 출발

이전의 입력(vPass)에서 2의 입력이 있었는지 확인 후 없으면 3 제거

이전의 입력(vPass)에서 4의 입력이 있었는지 확인 후 없으면 7 제거

이전의 입력(vPass)에서 5의 입력이 있었는지 확인 후 없으면 9 제거

현재의 입력 1을 포함하여 지금까지 입력되었던 값은 중복해서 도달할 수 없으므로 현재의 값 1을 포함하여 입력되었던 값 제거 

 

현재의 숫자가 2가 입력되었을 경우를 다음번에 입력될 수 있는 숫자 목록을 구해보자.

현재 숫자 2가 입력되었다면, 다음번에는 1, 3, 4, 5, 6, 7, 9 에 직선상으로 도달할 수 있다. 그러나 8의 경우 5가 입력된 적이 있을 때에만 도달할 수 있다.

 

따라서 2의 입력 뒤에 도달할 수 있는 다음번 수의 목록은 다음과 같이 처리한 결과가 된다.

 

일단 1, 2, 3, 4, 5, 6, 7, 8, 9로 출발

이전의 입력(vPass)에 5의 입력이 있었는지 확인 후 없으면 8 제거

현재의 입력 2를 포함하여 지금까지 입력되었던 값은 중복해서 도달 할 수 없으므로 현재의 값 2를 포함하여 입력되었던 값 제거

 

해당 과정으로 나머지 숫자들에 대한 다음번 수 목록을 구한다. 입력이 진행될 때마다 다음번 도달 가능한 수를 구해놓고, 다음 입력이 들어왔을 때 도달 가능한 수가 아니면 "NO"를 출력한다. 모든 입력이 매 도달 가능한 수에 포함되었을 때, "YES"를 출력한다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;
using ii = pair<int, int>;

vector<bool> getNextPoss(vector<bool> &vPass, int num) {

    vector<bool> vRe(10, true);

    vector<ii> vCheck;
    if (num == 1)
        vCheck = {{2, 3}, {4, 7}, {5, 9}};
    else if (num == 2)
        vCheck = {{5, 8}};
    else if (num == 3)
        vCheck = {{2, 1}, {5, 7}, {6, 9}};
    else if (num == 4)
        vCheck = {{5, 6}};
    else if (num == 6)
        vCheck = {{5, 4}};
    else if (num == 7)
        vCheck = {{4, 1}, {5, 3}, {8, 9}};
    else if (num == 8)
        vCheck = {{5, 2}};
    else if (num == 9)
        vCheck = {{5, 1}, {6, 3}, {8, 7}};

    for (int i=0; i<vCheck.size(); i++)
        if (!vPass[vCheck[i].first]) vRe[vCheck[i].second] = false;

    vPass[num] = true;
    for (int i=1; i<=9; i++) 
        if (vPass[i]) vRe[i] = false;
    return vRe;
}

int main() {

    int N;
    scanf("%d", &N);

    vector<bool> vPass(10), vPoss(10);
    for (int i=0; i<N; i++) {

        int n;
        scanf("%d", &n);

        if (i > 0 && !vPoss[n]) {
            printf("NO\n");
            return 0;
        } 
        vPoss = getNextPoss(vPass, n);
    }
    printf("YES\n");
    return 0;
}