백준 1039 교환

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

1039번: 교환

k번을 전부 돌려야 해서 조금 까다로운 문제였습니다. 1,000,000 이하의 수이므로 사실상 6자리라 보면 스왑하는 경우는 총 6C2=15, 10번 진행하므로 나올 수 있는 전체 경우는 15^10개입니다.

 

하지만 이를 모두 확인하는 것은 시간초과가 뻔하므로 (15^10 => 얼추 2^40 정도) 중복을 피해야합니다. 

(ex. 111 은 어떤 경우라도 스왑 시 111 이런 경우를 최소화시켜야 한다.)

 

bfs와 set을 이용해 풀었습니다.

각 라운드 (k번 라운드) 마다 set을 초기화하고 bfs를 이용해 스왑을 진행합니다. 동일 라운드에서 스왑한 것이 set에 포함되어 있다면 해당 값은 더 이상 진행해봤자 동일한 값이 나오므로 set에 넣지 않습니다.

 

그리고 마지막 라운드에서 큐에 남아있는 값들을 비교해 최대값을 고릅니다.

 

-1이 정답인 경우는 1자리 수이거나 2자리 수인데 1의 자리가 0이면 스왑이 불가능하므로 이 경우들은 -1이 정답입니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <cstring>
#include <algorithm>

using namespace std;

string n;
int k;
string ans;

void init()
{
    cin >> n;
    cin >> k;
    ans = "";
}

void bfs()
{
    // k번 진행하면서
    // 스왑시킨 것들 전부 큐에 넣기
    // set에 존재하면 동일한 케이스이므로 패스 
    set<string> check;
    set<string>::iterator iter;
    
    queue<string>q;
    
    q.push(n);
    int start = 0;
    int last = n.size() - 1;
    
    for(int i = 0; i < k; i++) {
        
        check.clear();
        
        // k번 진행한 거 구분하기 위해 
        // 이전 큐 사이즈만큼만 진행 
        int q_size = q.size();
        for(int j = 0; j < q_size; j++) {
            string tmp = q.front();
            q.pop();
            
            for(int u = start; u < last; u++) {
                for(int v = u + 1; v <= last; v++) {
                    string swap_tmp = tmp;
                    swap(swap_tmp[u], swap_tmp[v]);
                    
                    iter = check.find(swap_tmp);
                    // 스왑한 거 set에 없음 
                    if(iter == check.end()) {
                        check.insert(swap_tmp);
                        q.push(swap_tmp);
                    }
                }
            }
        }
        
        // k번 진행 시 최대값 구하기 
        if(i == (k - 1)) {
            ans = q.front();
            while(!q.empty()) {
                string tmp = q.front();
                q.pop();
                if(tmp > ans)
                    ans = tmp;
            }
        }
    }
    
    cout << ans;
}

bool fail()
{
    // 불가능한 경우
    // 1자리는 스왑 불가 
    if(n.size() == 1)
        return true;
    // 2자리인데 1의 자리가 0이어도 스왑 불가 
    if(n.size() == 2 && n[0] != '0' && n[1] == '0')
        return true;
    // 나머지는 가능 
    return false;
}

int main()
{
    init();
    
    if(fail())
        cout << -1;
    else
        bfs();
}