[1039] 교환

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

1039번: 교환

<문제>

연산 도중에라도 맨 앞에 0으로 시작하는 정수가 만들어지면 안된다.

정답 업데이트는 정확히 연산을 'K번' 수행했을때에만 업데이트 해주며,

string간의 사전순 비교로도 가능하지만, 1'000'000이하의 범위이니 int로 비교해주었다.

상태를 (숫자, 연산횟수)로 놓고, M^2으로 string을 swap해서 나온 결과를 모두 찾는다.

만들 수 있는 상태가 굉장히 희소하기 때문에, set으로 방문처리를 하는것도 나쁘지 않은 방법으로 보인다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

typedef struct {

    int num, turn;

} state;

string base;

int k, ans = -1;

bool vst[1000001][11], flag = false;

queue<state> q;

string f(string base, int i, int j) {

    base[i] ^= base[j];

    base[j] ^= base[i];

    base[i] ^= base[j];

    return base;

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> base >> k;

    int i, j, S = base.length();

    q.push({stoi(base), 0});

    vst[stoi(base)][0] = true;

    while (!q.empty()) {

        state cur = q.front();

        q.pop();

        if (cur.turn > k) continue;

        if (cur.turn == k) ans = max(ans, cur.num);

        for (i = 0; i < S; i++) {

            for (j = 0; j < S; j++) {

                if (i == j) continue;

                string nxt = f(to_string(cur.num), i, j);

                if (nxt.front() == '0') continue;

                if (vst[stoi(nxt)][cur.turn + 1] == false) {

                    vst[stoi(nxt)][cur.turn + 1] = true;

                    q.push({stoi(nxt), cur.turn + 1});

                }

            }

        }

    }

    cout << ans;

    return 0;

}