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

백준의 교환(1039) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 생각보다 헷갈리는 부분이 있었던 문제이다. 먼저, 이 문제를 보면 K번 숫자를 바꾸는 연산을 진행했을 때, 최댓값을 구하는

   문제이다. 그렇다면, 숫자를 K번 동안 바꾸는 과정에서 최댓값을 구하는문제일까 아니면 무조건 K번을 바꾼 후에 나온 값들

   중에서 최댓값을 구하는 문제일까? 정답은 후자이다. 우리가 K번 바꾸는 동안 최댓값을 찾는 것이 아닌, K번 바꾼 후에 나온

   값들 중 최댓값을 찾아야 한다.

   예제입력2를 한번 봐보자. 주어진 입력은 132 이고, 3번을 바꾸라고 되어있다.

   대략 머리속으로 대충 계산만 해봐도, 3번 이내에 최댓값은 321이 될 것 같지만, 정답은 312이다. 즉, 최댓값을 K번 바꾼 후에

   나온 연산들 중 찾는 것이다. (321은 3번째 연산이 아닌, 2번만 바꿨을 때 나오는 결과임)

   우리는 여기서 하나를 더 알고 가보자. 정답인 312는, 사실 1번만 바꿨을 때도 나올 수 있는 결과이다. 132 에서 1과 3을 바꿔버리

   면 312 라는 결과가 나온다. 우리가 만약 여기서, 312라는 결과를 이미 탐색했다고 체크해버린다면 어떻게 될까?

   아마 3번째 연산에서는 312를 탐색하지 못할 것이다. 이미 탐색했다고 체크해 버렸기 때문이다.

   즉, 우리는 "특정 단계에서 특정 값을 탐색했다고 체크해주더라도, 그 다음 단계로 넘어가면 이 체크를 무의미하게

   만들어줘야 한다." 분명히, 같은 단계 내에서 312 라는 값이 계속해서 체크된다면 그것은 시간, 메모리 낭비일 것이다.

   따라서, 우리는 매 단계마다 체크를 해주고 다시 체크를 풀어주는 과정이 필요하다.

2) 이제 본격적으로 문제를 풀어보자.

   본인은 주어진 숫자를 string으로 관리해주었다. string으로 관리하였을 때의 편한점은 숫자를 바꾸는 과정이 편하다.

   string은 각 문자들이 Indexing되기 때문에, 123의 경우 string[0] = 1, string[1] = 2, string[2] = 3 이런 식으로

   각 숫자들이 Indexing되어, swap하기에 굉장히 편한 점이 있다.

   또한, 범위가 10000000 이다. 숫자를 바꾸는 과정에서 저 보다 훨씬 큰 숫자들이 충분히 나타날 수 있고, 이는 탐색 체크를 위해서

   Visit[] 배열을 사용하게 되면, 배열의 크기가 너무 커져서 제대로 체크를 못하는 경우가 발생할 수 있다.

   따라서 본인은 string형으로 관리해주면서 set을 이용해서 방문 체크를 해 주었다.

  

   본인은 BFS로 풀이하였는데, Queue는 string변수를 관리하도록 만들어주었다. 처음 입력되는 값을 Queue에 string화 시켜서

   넣어주고 시작하였다. 이 때, Queue에서 반복과정을 설정할 때, 보통 조건문을 while(Q.empty() == 0) 이라고 설정해주는데,

   여기서 조건을 하나 더 넣어 주었다. while(Q.empty() ==0 && Cur_K < K) 로 설정해주었다. K는 우리가 입력받은 연산의

   횟수이고, Cur_K는 내가 지금 몇번 연산을 했는지를 Count하는 본인이 만든 변수이다. Queue가 비어있지 않더라도, 우리는 굳이

   K번 이상의 연산을 할 필요가 없기 때문이다.

   이 후, BFS-Leveling_Skill을 통해서 현재 Queue에서 바꿀 수 있는 모든 경우를 해주었다. 모든 경우를 진행하고 난 후에는,

   Cur_K 변수의 값을 ++ 시켜주었고, Queue의 while문이 돌 때마다, 중복체크를 해주는 set을 새로 설정해주었다.

  

   사실 이 문제에서는 중복체크를 해주는 저 부분만 조심하면 어렵지 않은 문제라고 생각한다.

   이것만 기억하면서 풀어보자. "중복체크를 해 주되, 현재 단계에서만 중복체크를 해주자 ! 다음 단계까지 영향을 미치면 안된다"

   이 사실만 기억하면 쉽게 풀 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<vector>
 
#define endl "\n"
#define MAX 1000000 + 1
using namespace std;
 
string Inp;
int K, M;
vector<int> Answer;
 
int Invert(string S)
{
    int Sum = 0;
    for (int i = 0; i < S.length(); i++)
    {
        Sum = Sum + (S[i] - '0');
        if (i != S.length() - 1) Sum = Sum * 10;
    }
    return Sum;
}
 
void Input()
{
    cin >> Inp >> K;
    M = Inp.length();
 
    if (M == 1 || (M == 2 && Invert(Inp) % 10 == 0))
    {
        cout << "-1" << endl;
        exit(0);
    }
}
 
void BFS(string S)
{
    queue<string> Q;
    Q.push(S);
    int Cur_K = 0;
    int Max = 0;
 
    while (Q.empty() == 0 && Cur_K < K)
    {
        int Qs = Q.size();
        set<string> Visit;
 
        for (int q = 0; q < Qs; q++)
        {
            string Cur = Q.front();
            Q.pop();
 
            for (int i = 0; i < M - 1; i++)
            {
                for (int j = i + 1; j < M; j++)
                {
                    if (i == 0 && Cur[j] == '0') continue;
 
                    swap(Cur[i], Cur[j]);
                    if (Visit.find(Cur) == Visit.end())
                    {
                        if (Cur_K == K - 1 && Max < Invert(Cur))
                        {
                            Max = Invert(Cur);
                        }
                        Q.push(Cur);
                        Visit.insert(Cur);
                    }
                    swap(Cur[i], Cur[j]);
                }
            }
        }
        Cur_K++;
    }
 
    if (Cur_K != K) cout << "-1" << endl;
    else cout << Max << endl;
 
}
 
void Solution()
{
    BFS(Inp);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}