교환

BOJ 교환 1039

BFS

문제 잘 읽는게 중요한 듯

[-] Collapse

#include<iostream>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
bool visit[1000001];
int main(){
    int k; string ans;
    cin >> ans >> k;
    queue<string> mq; mq.push(ans); visit[stoi(ans)] = true;
    while (k){
        int size = mq.size();
        memset(visit, false, sizeof(visit));
        for (int i = 0; i < size; i++){
            string tstr = mq.front(); mq.pop();
            if (tstr[0] == '0') continue;
            for (int i = 0; i < tstr.length(); i++){
                for (int j = i+1; j < tstr.length(); j++){
                    if (i == 0 && tstr[j] == '0') continue;
                    string qstr = tstr;
                    swap(qstr[i], qstr[j]);
                    int toInteger = stoi(qstr);
                    if (!visit[toInteger]){
                        mq.push(qstr);
                        visit[toInteger] = true;
                    }
                }
            }
        }
        k--;
    }
    ans = "0";
    while (!mq.empty()){
        if (ans < mq.front()) ans = mq.front();
        mq.pop();
    }
    if (ans[0] == '0') cout << -1;
    else cout << ans;
}