[백준] 1039번 교환

1039번: 교환

연산 횟수를 1씩 증가해주며 현재 횟수로 만들 수 있는 숫자들을 모두 임시 큐에 넣어주고

메인 큐가 empty할 때까지 반복한 뒤 빠져나오면 임시 큐의 값들을 전부 메인 큐에 넣어준다.

연산 횟수가 K가 되면 빠져나와 최댓값을 출력해주는데

최댓값의 default를 -1로 해주면

연산을 K번 할 수 없는 경우엔 최댓값이 변하지 않아 문제에서 바라는 대로 -1을 출력할 수 있다.

ex) 숫자는 10이고 K는 1일 때

 

이때 주의할 점은 방문 체크하는 부분이다.

현재 메인 큐를 다 비우고 나면 다음 메인 큐에서 할 연산은 현재 메인 큐와 상관없으므로

방문 체크 해주었던 visited도 초기화를 해주어야 한다.

또한 연산 전 숫자와 연산 후 숫자와 같을 수도 있다는 것을 알아야 한다.

ex) 110 -> 1(첫 번째 위치)과 1(두 번째 위치) 자리 교환 => 110

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int Max = -1, cnt = 0, K;
string num;
queue <string> q, tmp;
void Bfs(int M) {
	while (1) {
		if (cnt == K) break;
		cnt++;
		bool visited[1000001] = { false };
		while (!tmp.empty()) {
			q.push(tmp.front());
			tmp.pop();
		}
		while (!q.empty()) {
			for (int i = 0; i < M - 1; i++) {
				for (int j = i + 1; j < M; j++) {
					num = q.front();
					if ((i == 0 && num[i] != '0' && num[j] != '0') || i > 0) {
						swap(num[i], num[j]);
						if (!visited[stoi(num)]) {
							if (cnt == K) Max = max(Max, stoi(num));
							visited[stoi(num)] = true;
							tmp.push(num);
						}
					}
				}
			}
			q.pop();
		}
	}
}

int main() {
	string N;
	cin >> N >> K;
	q.push(N);
	Bfs(N.size());
	cout << Max;
	return 0;
}