백준 1103번 문제와 유사하다고 느꼈던 문제
완전탐색+가지치기가 필요하다.
https://www.acmicpc.net/problem/1103

문제 설명

수 N이 주어질 때 K번만큼 두 자릿수를 교환해서 가장 최대가 되는 수를 구해야 한다.

ex.
132 3
-> 312

풀이

처음에는 매 단계마다 수가 최대가 되도록 greedy하게 풀면 풀릴 거라고 생각했다.

하지만.. 다음의 경우에서 문제가 발생했다.

8799 2

정답) 9987
내 답) 9978

이전 단계에서 수가 가장 컸다고 해서 다음 단계에서도 가장 크게 만들 수 있다는 보장이 없었다.

그리디하게 푸는 게 모든 케이스에서 옳을까? 라는 의구심을 가지면서도 마땅한 방법이 생각이 안나서 이렇게 풀었던 건데.. 역시나 틀렸다.

결국 완전탐색을 해야 하는데, 최악의 경우 시간복잡도가 7C2^10이 되는 문제가 발생한다. 시간 안에 문제를 풀 수 없기 때문에 중복되는 경우는 skip해줘야 한다.

그래서 각 단계에서 이미 봤던 수라면 skip할 수 있도록, visit[i][j] 배열을 만들어서 j단계에 i를 이미 봤다면 skip하도록 했다.

이렇게 만들면 각 단계에서 봐야 하는 수는 아무리 naive하게 생각해봐도 7!이고 최대 10단계이므로 7!*10개정도 확인하는 건 크게 문제가 되지 않는다.

기억해둬야 할 건
완전탐색 문제에서 시간복잡도를 줄이기 위해서는 봤던 경우는 또 다시 보지 않도록 만들면 된다!!

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int k, s_len, maxx = 0;
bool visit[1000001][11]; // j단계에 i를 방문했는지 여부를 저장
queue<pair<string, int>> q; // {string, cnt}

void bfs(string s, int cnt) {
    q.push({s, cnt});
    visit[stoi(s)][cnt] = true;
    while (q.empty() == false) {
        string curr_str = q.front().first;
        int curr_cnt = q.front().second;
        q.pop();
        if (curr_cnt == k) {
            maxx = max(maxx, stoi(curr_str));
            continue;
        }
        for(int i = 0; i < curr_str.length(); i++) {
            for(int j = i + 1; j < curr_str.length(); j++) {
                swap(curr_str[i], curr_str[j]);
                if (!visit[stoi(curr_str)][curr_cnt + 1] && to_string(stoi(curr_str)).length() == s_len) { // 이미 방문한 노드가 아니고 자릿수가 달라지지 않으면 push
                    q.push({curr_str, curr_cnt + 1});
                    visit[stoi(curr_str)][curr_cnt + 1] = true;
                }
                swap(curr_str[i], curr_str[j]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    string s;
    cin >> s >> k;
    s_len = s.length();
    bfs(s, 0);
    if (maxx == 0) cout << -1;
    else cout << maxx;
}