[백준] 1039: 교환

0. 문제 주소

 

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

1039번: 교환

 

 

1. 풀이

 

풀이 검색해보고 신세계였던 문제.

 

'level 별로 보는 BFS'라는데 이 말만 들으면 헷갈리니까 예시를 들어보자.

 

 

 

우선 문제에선 K번 바꾸는 동안의 최댓값이 아니라, 정확히 K번을 바꾼 후의 최댓값을 묻고 있다.

 

A라는 숫자에서 i번째 swap을 통해 B를 얻었다고 하자. 앞으로 K-i번의 swap을 더 해야 한다.

 

앞으로 해야 할 K-i번의 swap의 모든 결과값들 중에, B가 나오면 안 될까? 그렇지 않다.

 

 

예를 들어, sample case의 N = 132, K = 3인 경우를 보자.

 

1과 3을 바꾸어 312가 되었고, 1과 2를 바꾸어 321을 만든다. 하지만 K = 3이므로 한 번의 swap을 더 해야 하고,

 

여기서 2와 1을 또 바꾸어 다시 312을 만든다. 

 

이것을 그래프 순회의 관점에서 보면, 이미 방문했던 312라는 정점을 다시 한 번 방문한 것과 같다고 할 수 있다.

 

 

보통 BFS의 경우엔 312는 1번째 swap에서 방문했었으니까, 3번째 swap에서 312가 나오는 경우는 생각하지 않는다.

 

하지만 이 문제의 경우엔 그렇지 않다.

 

i번째 swap에 대해서, i를 level이라고 본다면, 서로 다른 level에서는 같은 수가 나와도 탐색해봐야 한다.

 

거꾸로 말하면, 동일한 회차의 swap에서 동일한 결과가 나왔을 때만 이미 방문했던 노드처럼 생각하고 탐색을 생략한다.

 

나는 swap의 편의성을 위해 N을 string으로 처리했고, 이번 회차의 swap에서 봤었던 string을 체크하기 위해 set을 사용했다.

 

 

 

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define MAX 20005

using namespace std;

string str;
int K;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> str >> K;

    queue<string> q;
    q.push(str);

    for (int x=0;x<K;x++){
        int q_size = q.size();
        set<string> s;
        for (int n=0;n<q_size;n++){
            string curr = q.front();
            q.pop();
            if (s.count(curr)) continue;
            s.insert(curr);

            for (int i=0;i<str.size()-1;i++){
                for (int j=i+1;j<str.size();j++){
                    if (i>0 || curr[j] != '0'){
                        swap(curr[i], curr[j]);
                        q.push(curr);
                        swap(curr[i], curr[j]);
                    }
                }
            }
        }
    }

    string ans = "0";

    while(!q.empty()){
        ans = max(ans, q.front());
        q.pop();
    }
    if (ans[0] == '0') cout << "-1\n";
    else cout << ans;

    return 0;

}