[백준] 1039번 교환 [C++]

 

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

1039번: 교환

---

문제

백준 1039번

 

 

---

접근 방법

 

BFS를 이용하여 문제를 해결하였다.

먼저 , 0번 교환했을 때의 초기 문장을 큐에 넣고, 그 안에서 각각의 자릿수를 교환한 문장을 만든후 큐에 넣어준후 팝 해준다.

그 후 1번 교환했을때의 문장들이 Q에 있으므로, 다시 자릿수를 교환한 후 큐에 넣어준 후 팝해준다.

...를 N번 교환까지 진행 해 준다.

큐에 넣을때 예외처리 해 줄 부분이 있는데

• 교환 한 후 문장의 맨 처음이 0일 때
• 문장의 길이가 1이여서 교환을 할 수 없을때

는 각각 "-1"을 반환하며 큐에 넣지 않는다.

 

N번 교환한 값 중에 가장 큰 문장을 출력해주면 된다.

 

주의사항

처음에 flag없이 큐에 넣었다가 메모리초과가 발생하였다. 이러한 경우는

교환한 횟수가 같고, 결과가 같은 값들 모두 큐에 들어가면 큐에 너무 많은 값이 들어가게 되어서 이다.

메모리초과를 방지하기 위해서 교환횟수도 같고, 결과값도 같은 경우가 큐에 들어가는것을 방지하기 위해서 Flag를 만들어서, 이미 들어간 값이 더 못 들어가게 해주었다.

 

---

코드

#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
int n,m;
string maxs="-1";
bool flag[10000000][11];
string swap(string s2,int a, int b) {
	if (s2.length() == 1)return "-1"; //예외처리 ->문장의 길이가 1일경우 교환이 불가능함
	char c1 = s2[a];
	char c2 = s2[b];
	s2[a] = c2;
	s2[b] = c1;
	if (s2[0] == '0')return "-1"; //예외처리 ->교환 후 문장의 맨 앞이 0일경우 
	return s2;
}
int main() {
	string s;
	cin >> s >> n;
	int sLength = s.length();
	queue<pair<string,int>> q;
	q.push({ s,0 });
	while (!q.empty())
	{
		string s2 = q.front().first;
		int k = q.front().second;
		if (k == n) {
			maxs = max(s2, maxs);
		}
		q.pop();
		for (int i = 0; i < sLength-1; i++) {
			for (int j = i + 1; j < sLength; j++) {
				string s3=swap(s2, i, j);	
				if (s3 != "-1"&&k<n&&!flag[stoi(s3)][k+1]) { //결과가 -1이면 상기 적은 예외
					flag[stoi(s3)][k+1] = true;
					q.push({ s3,k + 1 });
				}
			}
		}
	}	
	cout << maxs;
}

---

 

 

BFS와 문자를 활용한 문제였다.