백준 1039번 교환 C++

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

 

숫자를 몇번 바꿨는지 정보까지 이용해서 방문 배열을 2차원으로 사용해서 bfs를 통해 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, k;

vector<vector<bool>> found;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> k;
    found = vector<vector<bool>>(1000001, vector<bool>(k + 1, false));

    queue<pair<int, int>> q;
    q.push({ n,0 });
    found[n][0] = true;

    int ans = -1;

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        if (curr.second >= k) {
            ans = max(ans, curr.first);
        }
        string currStr = to_string(curr.first);
        if (curr.second < k) {
            for (int i = 0; i < currStr.length(); i++) {
                for (int j = i + 1; j < currStr.length(); j++) {
                    string nextStr = currStr;
                    ::swap(nextStr[i], nextStr[j]);
                    if (nextStr[0] == '0') continue;
                    int nextNum = stoi(nextStr);
                    if (found[nextNum][curr.second + 1]) continue;
                    q.push({ nextNum,curr.second + 1 });
                    found[nextNum][curr.second + 1] = true;
                }
            }
        }
    }
    cout << ans;
}