[BOJ] 17255 N으로 만들기

스스로 풀어낸 기쁜 문제이다.

 

방문 배열을 이차원으로 만들어서 layer마다 확인하도록 했다. BFS로도 풀어낼 수 있을 것 같다.

 

17255번: N으로 만들기

 

 

#include <iostream>
#include <string>
#define MAX 8
using namespace std;

string N; int cnt = 0, N_length;
string visit = "00000000";
bool layer_visit[MAX+1][10];

void input(){
    cin >> N;
    N_length = N.length();
}

void solve(int len, string cur, string v ){
    if( len == N_length ){

        if( cur == N )
            cnt++;
        return;
    }
    for(int i = 0 ; i < N_length ; i++){

        if(v[i] == '0' && !layer_visit[len][N[i] - 48] ){

            layer_visit[len][N[i] - 48] = true;
            v[i] = '1';

            if( cur + N[i] == N[i] + cur)
                solve(len+1, cur+ N[i], v );

            else{

                solve(len+1, cur+ N[i], v );
                solve(len+1, N[i] + cur, v);

            }
            v[i] = '0';

        }
    }
    fill_n(layer_visit[len], 10,0);


}
int main() {
    input();
    solve(0, "", visit);
    std::cout << cnt << std::endl;
    return 0;
}