1244. 최대 상금

십진수가 있을 때 i번째 자리와 j번째 자리를 swap할 수 있다고 하자. 이 연산을 k번 했을 때 만들 수 있는 최고값을 묻는 문제다.

bfs로 풀었다. 다만 숫자중에 같은 숫자가 2개 이상 있다면 k번째일때만 검사하는게 아니라 모든 경우가 최대값이 될 수 있기 때문에

(위치가 다른 같은 숫자를 swap한다면 횟수는 소모되지만 수는 그대로다) 그 경우를 고려해야 하고 같은 숫자가 없다면

k와 짝수만큼 차이나는 횟수도 모두 정답일 수 있으므로 고려해야 한다.

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
 
int rad(int x) {
    int ans = 0;
    while (x) {
        x /= 10;
        ans++;
    }
    return ans;
}
 
int t, n, k;
int d[1000001];
int p[7] = { 1,10,100,1000,10000,100000,1000000 };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        int c[10] = { 0, };
        memset(d, -1, sizeof(d));
        cin >> n >> k;
        queue<int> q;
        int nrad = rad(n), ans = n, f = 0;
        for (int i = 0; i < nrad; ++i) {
            c[(n / p[i]) % 10]++;
            if (c[(n / p[i]) % 10] == 2) f = 1;
        }
        q.push(n);
        d[n] = 0;
        while (q.size()) {
            int x = q.front();
            q.pop();
            if (d[x] == k) 
                break;
            for (int i = 0; i < nrad; ++i) {
                int x1 = (x / p[i]) % 10;
                for (int j = i + 1; j < nrad; ++j) {
                    int x2 = (x / p[j]) % 10;
                    int nx = x - x1 * (p[i] - p[j]) - x2 * (p[j] - p[i]);
                    if (d[nx] != -1) continue;
                    d[nx] = d[x] + 1;
                    q.push(nx);
                    if (f) ans = max(ans, nx);
                    else if ((k - d[nx]) % 2 == 0)
                        ans = max(ans, nx);
                }
            }
        }
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}