문제

N,K가 주어졌을때 N의 자리수를 K번 교환해보며 K번째 최대값을 구하는 문제다.

단순히 BFS를 통해 가지를 이어나가면 경의의 수가 굉장히 많아진다.
6숫자중 2개를 뽑으면 15인데 이게 10번 반복하면 15^10이다.

너무 큰 숫자이기에 가지를 적절하게 쳐줘야한다.

핵심은 각 스텝에서 중복을 없애는 것이다.
매 단계에서 중복을 없애면 해결할 수 있었다.
(또한 삼성문제처럼 안되는 조건을 찾는게 까다롭다.)

code

/*
백준 1039
10^6 이 최대값인데 결국은 6! = 720가지다
근데 visited를 다시 방문해야하지 않나..?
*/
#include <iostream>
#include <queue>
#include <map>
using namespace std;

int N, K,N_len;

int numLen(int num) {
	int res = 0;
	while (num != 0) {
		res++;
		num /= 10;
	}
	return res;
}

bool isOk() {
	// 1. 1자리
	if (N_len == 1)	return false;

	// 2. 2자리인데 1자리가 0인 경우
	if (N_len == 2 && (N % 10 == 0)) return false;

	return true;
}

int toNum(char arr[]) {
	int res = 0;
	for (int i = 0; arr[i]; i++) {
		res *= 10;
		res += arr[i] - '0';
	}
	return res;
}

int swapNum(int num, int l, int r) {
	char buf[16];
	sprintf(buf, "%d", num); // num을 buf에 넣게됨

	// swap
	char tmp;
	tmp = buf[l];
	buf[l] = buf[r];
	buf[r] = tmp;

	// 바꾼값이 0으로 시작하면 -1 반환
	if (buf[0] == '0') return -1;

	return toNum(buf);
}

int main(){
	cin >> N >> K;
	queue<int> que;
	map<int, int> map;
	que.push(N);

	// 처음부터 교환이 불가능한 경우 바로 출력
	N_len = numLen(N);
	if (!isOk()) {
		cout << -1;
		return 0;
	}
	for (int i = 0; i < K; i++) {
		int que_sz = que.size();
		map.clear(); // 각 스탭마다 중복 체크
		// 교환 진행
		for (int j = 0; j < que_sz; j++) {
			int num = que.front();
			que.pop();
			// N자리 중에서 2개를 골라 교환 (0,1) (0,2) ... (lastIdx-1,lasIdx)
			for (int a = 0; a < N_len - 1; a++) {
				for (int b = a + 1; b < N_len; b++) {
					int next_num = swapNum(num, a, b);
					if (next_num == -1) continue; // 불가능하면 패스
					if (map.find(next_num) != map.end()) continue; // 중복되면 패스
					map.insert({ next_num,next_num });
					//printf("[%d] %d\n", i, next_num);
					que.push(next_num);
				}
			}
		}
	}
	// que가 비어있으면 -1
	if (que.empty()) {
		cout << -1;
		return 0;
	}
	// que 안에서 최대값 출력
	int max_val = -int(1e9);
	while (!que.empty()) {
		int num = que.front();
		que.pop();
		max_val = (num>max_val) ? num : max_val;
	}
	cout << max_val;
	return 0;
}