[백준] 1039 - 교환

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

1039번: 교환

 처음엔 문제를 읽고 '연산을 K번 할 수 없다' 라는 의미가 뭔지를 이해하지 못해 한참 생각을 했다. 주어진 정수의 각 자리수를 바꿀때 자리수가 짧으면 K번을 교환할 수 없는 경우가 생긴다. 이에 대한 처리를 해줘야 하는데 K번의 최대값이 10이므로 BFS를 통한 완전 탐색이 가능할 것 같았다. 구현시 유의할 점은 다음과 같다. 

1. K번을 바꾼 뒤의 정수가 최대값이어야 하며, 바꾼 과정에서의 최대값은 의미가 없다.
2. BFS로 Queue에서 Push시에 바꾼 정수의 앞자리가 0인 것은 push해서는 안된다.
3. bfs의 종료 조건은 변경 횟수가 K가 되었을 때이다. 이때 bfs 탐색을 종료하고, Queue에 남아있는 아이템들을 pop하여 그중에 최대값을 골라낸다.

#include <iostream>
using namespace std;
#include <queue>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _num {
    int value;
    int step;
}num;
queue<num> nums;
bool visited[1000001][11];

int swap(int n, int i, int j){
    string ret = to_string(n);
    if(i==0 && ret[j] == '0') return -1;
    char temp = ret[i];
    ret[i] = ret[j];
    ret[j] = temp;
    return atoi(ret.c_str());
}

int main(){
    int N, K;
    memset(visited, false, sizeof(visited));
    scanf("%d%d", &N, &K);
    visited[N][0] = true;
    num first = {N, 0};
    nums.push(first);

    string str = to_string(N);
    int len = str.length();

    while(!nums.empty()) {
        num pop = nums.front();

        if(pop.step == K){
            break;
        }
        nums.pop();

        pop.step += 1;
        for(int i=0; i<len-1; ++i){
            for(int j=i+1; j<len; ++j){
                int change = swap(pop.value, i, j);
                if(change != -1 && visited[change][pop.step] == false){
                    visited[change][pop.step] = true;
                    num item = {change, pop.step};
                    nums.push(item);
                }
            }
        }        
    }

    int result = -1;
    while(!nums.empty()){
        if(result < nums.front().value) {
            result = nums.front().value;
        }
        nums.pop();
    }

    printf("%d\n", result);

    return 0;
}