[BOJ/백준 1039/C++] 교환

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

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을 출력한다.

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

이번 문제는 약간의 탐색의 변형?이 필요한 문제였다.

 

예를 들어 문제에서 예제로 주어진 (132, 3)의 경우를 생각해보면, 왠지 느낌상 정답이 321이 나올 것 같지만, 실제 정답은 312가 나와야한다.

 

첫번째 교환에서 3와1을 바꿔서 312를 만들고, 두번째 교환에서 1과 2를 교환해서 321를 만들고 마지막 교환에서 1과2를 다시 한번 교환해 312가 정답이 된다.

 

자세히 보면 변환하는 과정에서 같은 수가 중복되서 나오는 경우가 생길 수 밖에 없게 된다. 따라서 일반 탐색방법 처럼 이미 한번 만들었던 수에 대해서 check를 해주면서 교환을 하게 되면 문제에서 주어진 예제를 통과하지 못하게 된다.

 

따라서 이 문제는 중복 여부를 탐색을 진행하는 동안 계속 유지시키는 것이 아니라 BFS를 이용하여 탐색을 진행할때 레벨이 바뀌게 되면 중복 여부를 초기화 시켜주는 것이 핵심인 문제다.

BFS를 수행하면서 교환하는 모든 경우의 수를 생각하는 대신 중복은 같은 레벨에서만 체크해주는게 핵심인 문제였다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define mod 1000000
#define pii pair<int,int>

using namespace std;

string N;
int K;

typedef struct Node
{
	string cur;
	int depth;
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> K;
	
	queue<Node> q;
	q.push({ N, 0 });
	
	int ans = 0;
	vector<bool> ck(1000001, 0);
	
	int prev_depth = 0;
	while (!q.empty())
	{
		Node tmp = q.front(); q.pop(); int value = atoi(tmp.cur.c_str());
		if (tmp.depth == K)
		{
			ans = max(ans, atoi(tmp.cur.c_str()));
			continue;
		}

		if (prev_depth != tmp.depth)
		{
			for (int i = 0; i < ck.size(); i++) ck[i] = false;
		}
		prev_depth = tmp.depth;
	
		for (int i = 0; i < N.size() - 1; i++)
		{
			for (int j = i + 1; j < N.size(); j++)
			{
				string t = tmp.cur;
				char dummy;

				dummy = t[i];
				t[i] = t[j];
				t[j] = dummy;

				if (t[0] == '0') continue;
				if (ck[atoi(t.c_str())]) continue;

				ck[atoi(t.c_str())] = true;
				q.push({ t, tmp.depth + 1 });
			}
		}
	}
	if (ans == 0) cout << "-1";
	else cout << ans;
}

굳