C++ / 백준 / 1039 / 교환

문제

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

1039번: 교환

문제풀이

숫자를 string형으로 받고 BFS로 풀었다.

모든 경우를 탐색하면서 가장 큰 수를 갱신했다.

그러나 같은 숫자를 또 판별하게 되면 메모리 초과가 발생한다.

방문은 set을 이용하여 방문 처리를 하였다.

숫자를 바꿨을 때 맨 앞자리가 0이 아니고, 처음 본 숫자일 때만 큐에 넣도록 했다.

cnt +1 == K (숫자를 한번 바꿨을 때),

K - (cnt +1) % 2 == 0 일 때 (숫자를 한번 바꾼 후, 숫자를 두 번 바꾸면 같은 숫자가 되므로),

cnt % 2 == 0 (현재 숫자에서 두 번 바꾸면 같은 숫자가 되므로),

이렇게 세 가지 경우일 때 새로운 숫자가 answer값 보다 크다면 갱신하도록 했다.

 

반례: 900 2

 

 

코드

#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;

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

	string N("");
	int K(0);
	set<string>visit;
	queue<pair<string, int>>q;

	cin >> N >> K;	

	q.push({ N,0 });
	visit.insert(N);

	int idx(0), idx2(0);
	string answer("");

	while (!q.empty()) {
		string num = q.front().first;
		int cnt = q.front().second;
		q.pop();
		for (idx = 0; idx < N.size(); ++idx) {
			for (idx2 = idx + 1; idx2 < N.size(); ++idx2) {
				string n_num = num;
				swap(n_num[idx], n_num[idx2]);
				auto is_visit = visit.insert(n_num);
				if (n_num[0] != '0') {
					if (cnt + 1 <= K) {
						if (is_visit.second)
							q.push({ n_num, cnt + 1 });
						if ((K - (cnt + 1)) % 2 == 0)
							answer = max(answer, n_num);
						else if (cnt + 1 == K)
							answer = max(answer, n_num);
						else if (cnt % 2 == 0)
							answer = max(answer, num);
					}
				}
			}
		}
	}
	if (answer != "") cout << answer;
	else cout << -1;
}