백준 1039 - 교환 [C++]

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

1039번: 교환

---

풀이 과정

M자리 숫자 N에서 2개의 숫자의 위치를 K번 바꿨을 때 가능한 최대값을 구하는 문제이다.

 

한 숫자에서 교환해서 만들수 있는 모든 수를 탐색해가면서, K번 교환해서 만들 수 있는 수 중에서 가장 큰 값을 구해주면 된다. 일종의 BFS 문제이다.

 

---

소스 코드

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

int N, K, M;

int swap(int num, int a, int b) { // a자리 숫자와 b자리 숫자의 교환
    int aDivisor = pow(10, a);
    int bDivisor = pow(10, b);
    int aNumber = (num / aDivisor) % 10;
    int bNumber = (num / bDivisor) % 10;

    if (aNumber == 0 && b == M-1) return -1;

    return num - (aNumber*aDivisor + bNumber*bDivisor) + (aNumber*bDivisor + bNumber*aDivisor);
}

int main() {
    cin >> N >> K;
    int n = N;

    for (M = 1; M < 7; M++) { // N이 몇자리 수인지 M에 저장
        n /= 10;
        if (n == 0) break;
    }

    priority_queue<int> q[2]; // 최대 힙으로 K번째 교환시 가장 큰 수를 top으로 빠르게 탐색
    int t = 0, nt = 1; // 토글

    q[t].push(N);
    int prev = -1;

    for (int k = 0; k < K; k++) {
        prev = -1;
        while(!q[t].empty()) { // BFS
            int num = q[t].top();
            q[t].pop();

            if (num == prev) continue; // 같은 수를 2번 넣을 필요는 없다
            prev = num;

            int next;
            for (int a = 0; a < M; a++) { // 교환해서 만들 수 있는 모든 수를 힙에 저장
                for (int b = a+1; b < M; b++) {
                    next = swap(num, a, b);
                    if(next != -1) q[nt].push(next);
                }
            }
        }

        t = nt;
        nt = (nt + 1) & 1; // 힙 토글
    }

    if (q[t].empty()) cout << "-1\n";
    else {
        int result = q[t].top();
        cout << result << '\n';
    }

    return 0;
}