백준 1039번: 교환 (C++)

접근

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

1039번: 교환

C++을 하면서 처음으로 set을 이용해보았다. set이 중복되는 값을 입력받지 않는다는 점을 이용하여 아래의 문제 풀이에서 중복 체크하는데 사용하였다.

먼저 주어진 수를 string으로 바꿔서 문제를 풀이하였다. string의 경우 index를 이용하여 각 자리를 바꿀 때 간편하다는 점을 이용하기 위함이다. BFS 알고리즘을 이용하여 K회 자리 바꾸었을 때 가능한 모든 수를 탐색하여 그 수 중 가장 큰 수를 찾아내는 방법으로 문제를 해결하였다.

string을 저장하는 queue를 이용했으며, 큐에서 나오는 수가 예를 들어 4자리 수라면, 1번째와 2번째, 1번째와 3번째, 1번째와 4번째, 2번째와 3번째, 2번째와 4번째, 3번째와 4번째 자리수를 바꾼 수를 각각 새로운 큐에 추가해주게 된다. 그 과정에서 중복 추가를 제거해주기 위해 set을 이용하였으며, 바꾼 수가 set에 없을 경우에만 큐에 추가해주었다. 이 set은 바꾼 횟수가 변할 때마다 초기화해주게 된다.

코드

#include <iostream>
#include <queue>
#include <set>
#include <string>

using namespace std;

#define endl '\n'

int N, K, L;
string NN;

int max(int a, int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}

int BFS() {
    queue<string> Q;
    Q.push(NN);
    int MaxVal = 0;
    int Cur_K = 0;
    set<string> Visit;
    set<string>::iterator iter;

    while (Q.empty() == 0 && Cur_K < K) {
        int size = Q.size();
        Visit.clear();
        for (int s = 0; s < size; s++) {
            string Cur_S = Q.front();
            Q.pop();

            for (int i = 0; i < L - 1; i++) {
                for (int j = i + 1; j < L; j++) {
                    if (i == 0 and Cur_S[j] == '0') continue;
                    swap(Cur_S[i], Cur_S[j]);
                    if (Visit.find(Cur_S) == Visit.end()) {
                        Q.push(Cur_S);
                        Visit.insert(Cur_S);
                    }
                    swap(Cur_S[i], Cur_S[j]);
                }
            }
        }
        Cur_K++;
    }
    if (Cur_K != K) return 0;
    for (iter = Visit.begin(); iter != Visit.end(); iter++) {
        MaxVal = max(MaxVal, stoi(*iter));
    }
    return MaxVal;
}

int Solve() {
    L = NN.length();
    if (L == 1 || (L == 2 && N % 10 == 0)) {
        return 0;
    }
    return BFS();
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N >> K;
    NN = to_string(N);

    int ans = Solve();
    if (ans == 0) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!