백준 1039번 문제 ( 교환 )

문제 출처 : https://www.acmicpc.net/problem/1039

1039번: 교환

이 문제는 BFS 기법을 이용하여 문제를 해결했다.

string으로 입력을 받아서 정수로 전환하면서 문제를 해결했고 set 함수를 이용하여서 방문 배열처럼 사용하였다.

아래는 해당 문제를 풀이한 소스 코드이다.

#include<stdio.h>
#include<iostream>
#include<queue>
#include<string>
#include<set>
#pragma warning(disable:4996)
using namespace std;
string N;
int K;
int value;
int max_value;
void BFS(string str, int size)
{
    queue<string> que;
    que.push(str);
    while (!que.empty() && K != 0)
    {
        set<string> used;
        int que_size = que.size();
        K--;
        for (int i = 0; i < que_size; i++)
        {
            string temp = que.front();
            que.pop();
            for (int j = 0; j < size-1 ; j++)
            {
                for (int k = j + 1; k < size; k++)
                {
                    if (j == 0 && temp[k] == '0')
                        continue;
                    swap(temp[j], temp[k]);
                    if (used.find(temp) == used.end())
                    {
                        if (K == 0 && max_value < stoi(temp))
                            max_value = stoi(temp);
                        que.push(temp);
                        used.insert(temp);
                    }
                    swap(temp[j], temp[k]);
                }
            }
            
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> K;
    int size = N.size();
    if (size == 1 || (size == 2 && stoi(N) % 10 == 0))
    {
        printf("-1");
        return 0;
    }
    BFS(N,size);
    if (max_value == 0)
        printf("-1");
    else
        printf("%d", max_value);
    
}