[c++ 백준] (1039번) 교환

문제

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

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

1039번: 교환

---

풀이과정

• 다른 블로그의 풀이 과정을 참고하여 문제를 해결했습니다.
• 너비 우선 탐색을 이용하는데 방문 탐색 같은 경우 set을 이용하여 방문을 체크했습니다.
• BFS 안에서 반복문을 입력받은 K번 수만큼 수행을 하며 연산을 합니다.
• 반복문 안에서 set에 수가 없으면 넣고 연산을 진행하고 있으면 다음 수로 넘어갑니다.
• 수에 두 자리에 있는 값을 바꾸고 그 수를 queue에 넣는 식으로 나온 수를 queue에 채워 넣습니다.
• K번만큼 연산을 진행 한 뒤 남아 있는 queue에 있는 값을 비교하며 가장 큰 수를 찾습니다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <string>

#define endl "\n"
using namespace std;

string BFS(string start , int count)
{
	// 처음 입력 받은 문자열의 길이를 저장
	int length = start.size();
	// 너비 탐색을 위한 문자열 queue 생성
	queue<string> q;
	q.push(start);

	// 입력받은 k 수 만큼 반복문 실행
	for (int i = 0; i < count; i++)
	{
		// 방문을 체크 하기 위해 set 을 통해 방문 체크
		set<string> visit;
		int qsize = q.size();
		for (int i = 0; i < qsize; i++)
		{
			string start = q.front(); 
			q.pop();
			// set 에 수가 있으면 continue
			if (visit.count(start))
				continue;
			visit.insert(start);

			for (int a = 0; a < length - 1; a++)
			{
				for (int b = a + 1; b < length; b++)
				{
					// 0이 앞으로 오는 경우의 수 방지
					if (a == 0 && start[b] == '0') continue;
					// 자리를 바꾼후 queue 에 넣어 준 뒤 다시 자리를 바꿉니다.
					swap(start[a],start[b]);
					q.push(start);
					swap(start[a], start[b]);
				}
			}
		}
	}
	string answer = "0";
	// k 번 만큼 연산을 통해 만들어 진 수들을 비교하여 가장 큰 수를 출력합니다.
	while (!q.empty())
	{
		answer = max(answer, q.front());
		q.pop();
	}
	// 0으로 시작하는 수가 가장 큰 경우 -1 출력
	if (answer[0] == '0')
		return "-1";
	else
		return answer;
}

void Answer()
{
	string N;
	int K;
	cin >> N >> K;
	cout << BFS(N, K);
}

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