백준, BOJ, 1039번, 교환: C++ [CPP] ★★★

이것도 아주 중요한 문제라고 할 수 있다.

 

중복되는 값을 어떻게 골라내느냐이다.

 

 

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

---

 

#맞은 풀이

#include <iostream>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

int N, M, K;
int ans;

set<string> check[11]; //★★★★★★★

void func(string s, int cnt) {
    string after = s;
    int x = stoi(s); //string으로 받은 숫자.

    //K번 바꿨을 때.
    if (cnt == K) { ans = max(x, ans); return; }

    //바꿀 수 있는 모든 경우의수 확인
    for (int i = 0; i < M - 1; i++) {
        for (int j = i + 1; j < M; j++) {

            //첫번째 자리와 0은 바꿀 수 없음
            if (i == 0 && after[j] == '0')continue; //교환할 수 없는 경우 예외처리.

            swap(after[i], after[j]); //자리를 바꿈

            //count가 0이면 괄호 안은 1이됨. 즉, check 안에 없는 값일 경우(중복 x)
            if (!check[cnt].count(after)) {
                check[cnt].insert(after);
                func(after, cnt + 1);
            }

            //func을 실행하든 안하든 다시 원상태로.
            swap(after[i], after[j]); //다시 원상태로 복구함.(그래야 다른 것 조사 가능)

        }
    }
}

int main() {

    //입력
    string s;
    cin >> s >> K;
    M = s.size();
    N = stoi(s);
    // 주어진 수가 1자리 수일때 or 2자리이고 뒷자리 0 일때 (K는 자연수이기 때문)
    if (M == 1 || (M == 2 && s[1] == '0')) {
        cout << "-1";
        return 0;
    }
    else {
        func(s, 0);
        cout << ans;
    }


    return 0;
}

 

저기 별표친 부분이 제일 중요한 부분이다.

즉, 중복된 값에서는 백트래킹 가지를 쳐내는 것이다.

그렇다면 백트래킹이란 0단계부터 N단계까지 다 간다음.. N-1에서 다시 시작하고..

N-2에서 다시 시작하고.. 그러는데 어떻게 채워야 하느냐???

 

즉, cnt가 단계기 때문에 사용할 수 있는 것이다.

cnt가 단계라는 것을 단서로 삼아서 set 컨테이너로 중복없이 해당 set의 결과들을 담는다.

이미 나온 결과라면 시도하지 않는다가 핵심이다.

백트래킹은 항상 가지를 어떻게 치느냐에 따라 결정되는데 이 문제도 단계별로 결과를 저장한다?는 방식을 생각해야하는 좋은 문제다.