개요

백준 1039: 교환

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

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

접근 방식

1. 백준 1525번: 퍼즐 문제 처럼 수열을 문자열로 받아서 간단하게 자릿수를 바꾸려하였다.

2. 입력받은 K변수를 각 연산마다 하나씩 줄이며
   연산을 한 후에 K가 0이 되면 그때 큐에 들어있는 원소들이
   연산을 K번 하고 난 결과물들이다.
   해당 결과물들 중 제일 큰 값을 출력하게 구현을 하였다.

3. 하지만 방문여부를 확인하는 set을 선언해서 사용하였지만,
   방문했던 문자열을 다시 방문할수도 있으므로
   set을 적절히 초기화해야하지만 어디서 초기화해야할지를 몰랐다.

4. 검색해본 결과, 각 레벨 시작전에 초기화를 해야했다.
   고민해보니 각 레벨 안에서 방문했던 문자열은
   set에 넣어줌으로써 다시 방문하지 못하게 막고,
   새로운 레벨에서는 이전 레벨에서 방문한 문자열을
   방문할 수 있으므로 set을 초기화해준다.

코드

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

using namespace std;
//N, K , K번 바꿨을때 최대수
string N;
int K = 0, maxNum = -1;
//문자열 방문 set
set<string> visited;
void Input() {
	cin >> N >> K;
}

void Solution() {
	//bfs에 쓰일 queue
	queue<string> q;
	//초기값 push
	q.push(N);
	while (!q.empty()) {
		int qSize = q.size();
		//횟수 만큼만 연산해야하므로 -1
		K--;
		//연산 해준 값이 다음 번 연산 때 또 나올수 있으므로 각 연산전에 초기화해줌
		visited.clear();
		for (int i = 0; i < qSize; i++) {
			//큐에 들어가있는 숫자 cur에 넣어줌
			string cur = q.front();
			q.pop();
			//k는 j보다 무조건 커야함 (조건) 수의 크기는 문자열의 길이
			for (int j = 0; j < N.length() - 1; j++) {
				for (int k = j + 1; k < N.length(); k++) {
					string tmp = cur;
					//바꿨을때 앞자리가 0이오면 안됨
					if (j == 0 && tmp[k] == '0') continue;
					//자릿수 바꿔줌
					swap(tmp[j], tmp[k]);
					//set에 자리를 바꿔준 값이 없다면
					if (visited.find(tmp) == visited.end()) {
						//set에 넣어줌
						visited.insert(tmp);
						//큐에 푸시
						q.push(tmp);
					}
				}
			}
		}
		//연산횟수를 다 써서 K==0일 때
		if (K == 0) {
			//큐에 담긴 값들이 연산끝났을때 가능한 수들이므로
			while (!q.empty()) {
				int cur = stoi(q.front());
				//제일큰값 탐색
				maxNum = maxNum > cur ? maxNum : cur;
				q.pop();
			}
			cout << maxNum;
			return;
		}
	}
	// 반복문을 빠져나온다면 연산을 다했는데 K가 남아있는 경우로 -1 출력
	cout << -1;
}
int main() {
	Input();
	Solution();
}

문풀후생

계속 방문배열을 그대로 쓰던 문제만 풀어서 그런지
방문배열을 초기화해야한다는 개념이 좀 낯설고 어색하여 많이 헤멨다.
배웠으니 잘 써먹자