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

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

 

 

이 문제는 정수의 i번째 숫자와 j번째 숫자를 K번 변경하여서 만들 수 있는 가장 큰 숫자를 찾는 문제이다.

 

정확히 K번을 변경해야 하기때문에 그리디하게 맨 앞자리에서부터 큰 숫자를 찾아서 변경하는 방법이 불가능할 것 같다고 생각하였으며 N은 최대 100만으로 자리수가 6자리로 자리수를 변경하는 모든 경우의수를 찾으면 되지 않을까 생각하였다.

 

 

이를 해결하기 위해서 현재 숫자에서 나올 수 있는 숫자를 탐색하는 bfs(너비 우선 탐색)을 활용하였으며 K번(횟수)에 따라 나올 수 있는 수가 다르기 때문에 2차원 방문배열을 사용하여 방문체크를 하였다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, K;
int answer = -1;

void bfs() {
    queue<pair<string, int>> q;
    q.push({to_string(N), 0});
    vector<set<string>> visited(K+1);

    while(!q.empty()) {
        string value = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if(cnt == K) {
            int ans = stoi(value);
            answer = max(ans, answer);
            continue;
        }

        for(int i = 0; i < value.size(); i++) {
            for(int j = i + 1; j < value.size(); j++) {
                string tmp = value;
                char tmpch = tmp[i];
                tmp[i] = tmp[j];
                tmp[j] = tmpch;

                if(tmp[0] == '0') continue;

                if(visited[cnt+1].count(tmp)) continue;

                visited[cnt+1].insert(tmp);
                q.push({tmp, cnt+1});
            }
        }
    }
}

void solve() {
    bfs();

    cout << answer;
}

void input() {
    cin >> N >> K;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}