백준 1039번: 교환
문제
문제 바로가기> 백준 1039번: 교환
풀이
bfs를 이용하여 풀었고, 같은 것을 또 탐색하여 시간을 낭비하지 않기 위해 set을 이용하였다.
#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;
int k;
queue<string> q;
void swap(string &str, int left, int right){
char tmp = str[left];
str[left] = str[right];
str[right] = tmp;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
string str, ans = "0";
cin >> str >> k;
q.push(str);
for(int i=0; i<k; i++){
set<string> s;
int q_size = q.size();
for(int j=0; j<q_size; j++){
string item = q.front(); q.pop();
if(s.count(item)==1) continue;
s.insert(item);
for(int l=0; l<item.size()-1; l++){
for(int r=l+1; r<item.size(); r++){
if(l==0 && item[r]=='0') continue;
swap(item, l, r);
q.push(item);
swap(item, l, r);
}
}
}
}
while (!q.empty()){
ans = max(ans, q.front());
q.pop();
}
if(ans[0]=='0') cout << -1;
else cout << ans;
}
Author And Source
이 문제에 관하여(백준 1039번: 교환), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@danbibibi/백준-1039번-교환저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)