[백준/BOJ] 백준 1039번 : 교환

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

1039번: 교환

몇 번째 연산에서 어떤 수가 나왔는지를 통해 k번째 연산을 했을 때 나올 수 있는 수 중에서 가장 큰 수를 구한다

 

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;

string n;
int k;
int discovered[1000001][11];

int Solve(string number)
{
	int ret = -1;

	discovered[stoi(number)][0] = 1;

	queue<pair<string, int>> q;
	q.push(make_pair(number, 0));

	while (!q.empty())
	{
		pair<string, int> here = q.front();
		q.pop();

		//연산의 횟수가 k번을 넘었을때
		if (here.second > k)
			break;

		//연산의 횟수가 k번 일때
		if (here.second == k)
			ret = max(ret, stoi(here.first));

		//위치를 바꿀 i와 j를 고른다
		for (int i = 0; i < here.first.size(); i++)
			for (int j = i + 1; j < here.first.size(); j++)
			{
				char temp1 = here.first[i];
				char temp2 = here.first[j];

				string there_number = here.first;
				there_number[i] = temp2;
				there_number[j] = temp1;

				if (there_number[0] == '0')
					continue;

				pair<string, int> there = make_pair(there_number, here.second + 1);

				if (discovered[stoi(there.first)][there.second] == 0)
				{
					discovered[stoi(there.first)][there.second] = 1;
					q.push(there);
				}
			}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	memset(discovered, 0, sizeof(discovered));

	cin >> n >> k;

	cout << Solve(n);

	return 0;
}