[백준 1327번] [BFS / 비트마스킹] 소트 게임

Approach

최소 몇 개 선택하는지를 묻는 것에서 BFS 냄새가 났으면 충분하다. 다만, 기존에 처리한 숫자들은 다시 중복해서 처리할 이유가 없으므로 일종의 visited를 처리해야하는데 숫자들의 숫자는 8!밖에 안되는데 해당 숫자들을 전부 다 담기 위해서는 훨씬 더 큰 배열의 크기가 필요하게 된다. 따라서 set 자료구조를 활용해서 처리해주면 된다.

 

+ 숫자가 1~8까지 존재하므로 해당 숫자 - 1을 처리함으로써 총 3개의 비트로 해당 원소를 방문하였는지를 처리할 수 있다.

숫자가 8개이므로 총 24개의 비트를 가지고 visited를 처리할 수 있는 것이다. 위의 접근 방법 같은 경우는 string 자료구조를 써야하는 반면, 이 방식은 int 자료형으로도 처리할 수 있기 때문에 메모리 측면에서는 우위에 있다고 할 수 있겠다.

(참고 : https://blog.naver.com/jinhan814/222133470755)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    set<string> s;
    int n, k;
    cin >> n >> k;

    string ans = "";

    for(int i = 1; i <= n; i++){
        ans += to_string(i);
    }

    queue<string> q;

    string input = "";

    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        input += to_string(t);
    }
    q.push(input);

    int move_num = 0;
    while(!q.empty()){
        int q_size = q.size();
        for(int i = 0; i < q_size; i++){
            string cur = q.front();
            q.pop();
            if(cur == ans){
                cout << move_num << "\n";
                return 0;
            }
            
            for(int j = 0; j <= cur.size() - k; j++){
                string cmp = cur;
                reverse(cmp.begin() + j, cmp.begin() + j + k);
                if(s.find(cmp) == s.end()){
                    q.push(cmp);
                    s.insert(cmp);
                }
            }
        }
        move_num++;
    }
    cout << -1 << "\n";
    return 0;
}