백준 1327 - 소트 게임 (C++)

문제

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

1327번: 소트 게임

풀이

일단 BFS로 풀어야 한다는 건 알겠는데 도대체 방문배열을 어떻게 처리해야할지 감이 안 잡혔다.

큐에 배열이 포함되어야 할텐데 배열을 어떻게 들고 다녀야할지도 모르겠어서 답을 좀 참고했다.

배열은 문자열로 바꾸면 되고, 방문배열은 값 존재 여부 확인을 편하게 하기 위해 set으로 만들었다.

 

그외에는 일반 BFS와 유사하게 가능한 경우를 다 돌면서 큐에 저장하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int N, K;
set<string> visited;

string s = "";

int bfs(string str) {
    queue<pair<string, int>> q;
    visited.insert(str);
    q.push({str, 0});
    string target = str;
    sort(target.begin(), target.end());

    while (!q.empty()) {
        string cur = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if (cur == target) return cnt;

        for (int i = 0; i <= N - K; i++) {
            string tmp = cur.substr(i, K);
            reverse(tmp.begin(), tmp.end());
            tmp = cur.substr(0, i) + tmp + cur.substr(i + K, N - i + K);

            if (visited.find(tmp) == visited.end()) {
                visited.insert(tmp);
                q.push({tmp, cnt + 1});
            }
        }
    }
    return -1;
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        s += c;
    }
    cout << bfs(s);
}