백준 1039번 교환

< 백준 1039번 교환 - 마포 코딩박 >

사용한 알고리즘: BFS


 N자리 숫자가 주어지고, 이 숫자의 i번째와 j번째를 바꾸는 것을 K번 했을때 나올 수 있는 최대 숫자를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) (코드: 63~64)
 주어진 숫자가 1자리 수이거나, 2자리수이면서 뒷자리가 0인 경우 조건에 의해 바꾸는 행동을 할 수 없습니다. 이때 -1 을 출력합니다.

(2) (코드: 8~15)
 string으로 받은 숫자를 int로 변환해주는 함수를 하나 만들어줍니다.

(3) (코드: 17~57)
 x번 바꾼 숫자를 저장할 queue를 만듭니다.
 처음에는 0번 바뀐 (처음 입력받은) 숫자를 queue에 넣어줍니다.
 queue에 들어있는 x번 바뀐 모든 수를 꺼내 각 수의 모든 가능한 i<->j 바꾸기를 해준 후 다시 queue에 저장합니다.
 ( 이후 queue에는 x+1번 바뀐 모든 수가 들어있게됩니다.)

(4) (코드: Visit, 27줄)
 과정 (3)을 진행하며, set<string> 을 만들어 중복해서 저장하는 것을 피합니다.

(5) (코드: 43,44)
 K번 바뀐 수 중 최대를 답으로 출력합니다.

	#include <bits/stdc++.h>
	using namespace std;
	string S;
	int K, M;
	vector<int> Answer;
	// 문자열 S 를 숫자로 바꿈
	int Calcul(string S){
	int Sum = 0;
	for (int i = 0; i < S.length(); i++){
	Sum *= 10;
	Sum += (S[i] - '0');
	}
	return Sum;
	}
	void BFS(string S){
	queue<string> Q;
	Q.push(S);
	// 바꾼 횟수
	int cnt = 0;
	// 찾은 수 중 최대
	int ans = 0;
	while(!Q.empty() && cnt < K){
	int Qs = Q.size();
	// 똑같은 수 바꾸기 반복 방지 (메모리 초과 방지)
	set<string> Visit;
	// cnt=i 일때 i번 바뀐수들이 Q에 저장되어 있다.
	// 모든 i번 바뀐 수들을 한번씩 더 바꿔본다.
	for (int q = 0; q < Qs; q++){
	string now = Q.front();
	Q.pop();
	// 숫자 바꿔보기
	for (int i = 0; i < M - 1; i++){
	for (int j = i + 1; j < M; j++){
	// 0 으로 숫자가 시작하면 안된다.
	if (i == 0 && now[j] == '0') continue;
	swap(now[i], now[j]);
	if(!Visit.count(now)){
	// K번 바꾼경우 최대 수 찾기
	if(cnt == K-1)
	ans = max(ans,Calcul(now));
	Q.push(now);
	Visit.insert(now);
	}
	swap(now[i], now[j]);
	}
	}
	}
	cnt++;
	}
	if(cnt!=K) cout << -1 << endl;
	else cout << ans << endl;
	}
	int main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> S >> K;
	M = S.length();
	// 주어진 수가 1자리 수일때 or 2자리이고 뒷자리 0 일때
	if(M == 1 || (M == 2 && Calcul(S)%10==0))
	cout << "-1" << endl;
	else
	BFS(S);
	return 0;
	}

view raw BOJ 1039.cpp hosted with ❤ by GitHub