BOJ - 1039번 교환 (C++)

문제 출처: https://www.acmicpc.net/problem/1039

문제 난이도

Gold 3

문제 접근법

K번 연산이 끝난 후에 가장 큰 값을 출력하는 완전탐색 문제이다.
여기서 문제는 한 번 연산을 할 때 마다를 기억하고 마지막 연산까지 가서 최대값을 출력하는 것이다.
이를 위해 queue를 이용하고 queue.size(한 단계)만큼 반복문을 돌아 값을 저장한다.
이때, 반복문 체크를 위해 해쉬함수를 사용한다.

통과 코드

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

using namespace std;

int bfs(string s,int k) {
	queue<string> q;
	q.push(s);
	int M = s.size();
	int cnt = 0;
	int maxV = 0;
	while (!q.empty() && cnt < k) {
		int size = q.size();
		set<string> ch;
		while (size--) {
			string now = q.front();
			q.pop();
			for (int i = 0; i < M - 1; i++) {
				for (int j = i + 1; j < M; j++) {
					swap(now[i], now[j]);
					if (ch.find(now) == ch.end()) {
						int num = stoi(now);
						if (cnt == k - 1 && num > maxV) maxV = num;
						q.push(now);
						ch.insert(now);
					}
					swap(now[i], now[j]);
				}
			}
		}
		cnt++;
	}
	return maxV;
}

int main() {
	string N;
	int K;
	cin >> N >> K;
	if (N.size() == 1 || (N.size() == 2 && stoi(N) % 10 == 0)) {
		cout << "-1\n";
	}
	else {
		cout << bfs(N, K) << "\n";
	}
	return 0;
}

피드백

문제가 이해가 가지 않아 삽질했던 문제다. K번 돌리지 않아도 예제가 나오는데?하면서 3번후에 어떻게 최대값이 되는지 한참 살폈다!
다른 사람 코드를 참고해서 풀었고 0번이 맨 앞일 때 예외처리를 안해줬는데 통과했다. 통과도 통과지만 다음에는 예외처리 빼먹지않게 조심하자!