[백준] 1039-교환(C++)

문제링크: https://www.acmicpc.net/problem/1039

1039번: 교환

 

bfs문제입니다.

 

접근방식

 

1. 일반적인 공식이나 규칙을 통해서 풀 수 있는 문제가 아님

132 3

이라는 입력값일때, 결과는 321이 아닌 312

312 -> 321 -> 312 이기 때문에

 

즉, 특정 규칙을 통해서가 아닌 모든 경우를 판단해서 최대값을 도출하는 방향으로 접근함

 

2. bfs를 통해서 매번 k번만큼 모든경우를 판단해줌 

 

visited는 k번마다 초기화를 시켜주어야함.

왜냐하면 앞선 예시에서 312라는 값이 앞에서 사용되어졌는데, 결과값이기도 함 

즉, 매번 방문여부를 초기화하며 진행해주어야함 

 

문제풀이 

 

1. 우선 -1인 경우를 생각해봄

• 한자리 수일때: 스왑할 수가 없으니 불가
• 두자리 수이고 일의 자리수가 0일때: 스압하게 되면 0이 앞으로 나옴으로 조건에 부합하지 않음 ex) 10, 20, 50

    

2. BFS를 통해서 구현함

이때, K번만큼 반복하도록 구획을 나눠주면서 진행해야함. 이유는 접근방식 2번 참고

 

3. BFS에서 문자열에서 한 문자씩 바꿔보면서 visited집합에 값이 있는지 없는지 판단하며 진행

 

 

 

 

정답 코드

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

string arr;
int k;
int maxed = 0;
bool jud() {
	int cnt = 0;
	for (int i = 0; i < arr.size(); i++)
		if (arr[i] > '0')
			cnt++;
	if (cnt > 1)
		return true;
	return false;
}

void bfs() {
	queue <string> que;
	que.push(arr);

	for (int u = 0; u < k; u++) { // k번 반복 
		int sized = que.size();
		set <string> visitied;

		for (int s = 0; s < sized; s++) {
			string temp = que.front();
			que.pop();

			for (int i = 0; i < temp.size() - 1; i++) {
				for (int j = i + 1; j < temp.size(); j++) {
					if (i == 0 && temp[j] == '0') continue;

					swap(temp[i], temp[j]); // #include algo
					if (visitied.find(temp) == visitied.end()) {
						if (u == k - 1) { //마지막 턴
							int val = stoi(temp);
							maxed = max(maxed, val);
						}
						que.push(temp);
						visitied.insert(temp);
					}
					swap(temp[i], temp[j]);
				}
			}


		}



	}


}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> arr >> k;
	if (arr.size() == 1) { // 한자리 수
		cout << -1 << endl;
		return 0;
	}
	else if (arr.size() == 2 && jud() == false) { // 두자리 수이지만 수가 하나라 swap을 못할 때
		cout << -1 << endl;
		return 0;
	}

	bfs();

	cout << maxed << endl;

	return 0;
}