[백준/BOJ 알고리즘] 1039 교환 C++

> www.acmicpc.net/problem/1039

1039번: 교환

원래 이 문제를 풀 생각은 없었는데, 한 친구가 못 풀겠다고 같이 풀자고해서 풀게 되었다.

기존 그래프 탐색 문제와는 좀 다른 느낌이어서 나름 재밌게 풀었다. 

 

문제의 핵심 

• N은 최대 999,999 의 값을 갖는다. 즉 최대 6자리 자연수라는 것. K가 10보다 작으니, 전부 구해도 된다. 
• K번 연산을 한 동안 나온 최대값이 아닌, K번째 연산을 했을 때 나올 수 있는 최대값을 구해야한다.
• 큐를 이용하여 구현했는데, 큐에 담기게 될 것은, 각 자리의 숫자가 아닌 i (0<i<K) 번째 연산을 했을 때의 어떤 값이다.
• i가 같을 때 같은 숫자가 큐에 담길 필요는 없다. i가 다르다면 같은 숫자가 큐에 담겨도 된다.                                                          (즉, 방문 여부는 i 값이 변하는 시점마다 초기화 되어야한다.)

구현  

• 백만보다 작은 자연수를 보관하기 위한 배열을 생성하고, 첫번째 인덱스부터 큰 자리수의 값이 들어간다.
• 백만보다 작은 자연수의 방문여부와 몇번째 연산인지를 동시에 체크하기위해 이차원배열을 생성했다.
• 배열과 그 배열에 담긴 값을 int로 반환하는, int값을 배열에 넣는 두가지 메서드를 구현했다.

1. 이중 for문을 사용해 swap연산을 수행하고 큐에 푸시한 후 방문 체크한다.
2. 큐가 비어있거나, K번째 연산까지 마쳤을 때까지 반복한다.

 

> 코드가 궁금하다면, 포스트 하단의 더보기를 눌러주세요

 

 

* 코드에 대한 피드백은 언제나 환영합니다. *

#include <stdio.h>
#include <queue>
#include <math.h>
using namespace std;
#define MAX 1000001
#define DIVIDER 100000
typedef pair<int ,int> pr;
queue<pr> q;
int visited[MAX][11] = {};
int arr[10];

int __swap(int a, int b) {
    if( (!a && !arr[b]) || (!b && !arr[a]) ) return 0;
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
    return 1;
}

int toArray(int num) {
    int idx = 0, div = DIVIDER, q, mod, flag=0;
    while(1){
        q = num/div;
        mod = num % div;
        if(q || flag) {
            arr[idx++] = q; 
            flag = 1;
        }
        num = mod; 
        div/=10;
        if(!div) break;
    }
    return idx;
}

int toInt(int len) {
    int ans = 0, mul = pow(10,len-1);
    for(int i=0;i<len;i++){
        ans += arr[i]*mul;
        mul/=10;
    }
    return ans;
}

void solve(int n, int k, int len) {
    int lap=0, max = -1, cur, val, ans;
    q.push(make_pair(n, lap));
    visited[n][lap] = 1;
    
    while(!q.empty()) {
        cur = q.front().first;
        lap = q.front().second + 1;
        toArray(cur);

        if(lap > k) {
            while(!q.empty()) {
                if(q.front().second < k) {
                    q.pop();
                    continue;
                }
                if(q.front().second > k) break;
                ans = q.front().first;
                if(max < ans) max = ans;
                q.pop();
            }
            printf("%d\n",max);
            return;
        }
        for(int i = 0; i<len-1; i++) {
            for(int j= i+1;j<len;j++) {
                if(!__swap(i,j)) continue;
                val = toInt(len);
                __swap(i,j);
                if(visited[val][lap]) continue;
                q.push(make_pair(val, lap));
                visited[val][lap] = 1;
            }
        }
        q.pop();
    }
    printf("-1\n");
    return;
}



int main() {
    int n,k,len;
    scanf("%d %d",&n,&k);
    len = toArray(n);
    solve(n, k, len);
    
    return 0;
    
}