[백준] 16432 떡장수와 호랑이

 

하반기 코테를 위해 백준문제를 오랜만에 풀어봤따..!!

골고루 틀리면서 정신을 차리고 있다

 

이 문제는 dfs로 가장 1~n까지 간다고 생각하면 된다

대신 check[현재][이전에 고른 수]를 체크해 가며 가야한다

 

ans배열을 만들고 내가 수를 고르고 다음수로 넘어갈 때 현재의 수를 넣어주면

탐색이 끝나고 그대로 출력하면 된다

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int arr[1111][11];
bool check[1111][11];
int ans[1111];
 
bool solve(int pos,int prev){
    if(pos==n-1){
        for(int i=1;i<10;i++){
            if(i==prev) continue;
            if(arr[pos][i]){
                ans[pos]=i;
                return true;
            }
        }
    }
    for(int i=1;i<10;i++){
        if(i==prev) continue;
        if(arr[pos][i] && !check[pos+1][i]){
            check[pos+1][i]=true;
            ans[pos]=i;
            if(solve(pos+1,i)) return true;
        }
    }
    return false;
}
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d",&n);
    for(int i=0;i<n;i++){
        int k; scanf(" %d",&k);
        for(int j=0;j<k;j++){
            int a; scanf(" %d",&a);
            arr[i][a]=1;
        }
    }
    if(solve(0,0)){
        for(int i=0;i<n;i++) printf("%d\n",ans[i]);
    } else puts("-1");
}