[DFS] BOJ 1039 교환

https://www.acmicpc.net/problem/1039

1039번: 교환

 

문제 해결 알고리즘

 

dfs를 이용해 자리를 바꿔보고 K번 만큼 바꾼 후 가장 큰 값을 출력한다.

 

이 때 같은 수가 나올 수 있으므로 visited배열을 이용해 중복되는 값은 배제한다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

bool check[1000001][11];
string str; int m;
int result = 0;

void dfs(int K){
    if(str[0] == '0') return;
    if(K == 0){
        result = max(result, stoi(str));
        return;
    }

    for(int i=0;i<str.size()-1;i++){
        for(int j=i+1;j<str.size();j++){
            swap(str[i], str[j]);

            if(check[stoi(str)][K-1] == false){
                check[stoi(str)][K-1] = true;
                dfs(K-1);   
            }

            swap(str[j], str[i]);
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> str >> m;

    dfs(m);

    if(result == 0) cout << -1;
    else cout << result;
}