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

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 일단, 최소 횟수이고, 모든 경우를 생각해봐야 하기 때문에, BFS로 풀어야 한다.
2. 뒤집어 볼 수 있는 위치는 모두 뒤집어본다. 단, 뒤집었을 때 이미 테스트한 경로라면 그 분기는 거기서 끝낸다.
3. 이미 테스트한 방식은 set에 저장하여 확인한다.

---

⭐️ 정답 코드 및 설명

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

using namespace std;

int N, K;
queue<string> q;
set<string> isTest; // 이미 테스트한 항목들은 다시 테스트하지 않기 위한 목록

string input() {
    cin >> N >> K;
    string str = "";
    for (int i = 0; i < N; i++) {
        int s;
        cin >> s;
        str += to_string(s); // reverse 메서드를 쓰기 위해서 string으로 입력
    }
    return str;
}

bool isAsc(string str) {
    for (int i = 0; i < N; i++) {
        int temp = str[i] - '0';
        if (temp != i + 1) return false;
    }
    return true;
}

int bfs() {
    int size_ = N - K;
    int cnt = 0;
    while (!q.empty()) {
        cnt++;
        int q_size = q.size();

        // 한 회차를 1회 카운트로 하고 모두 돌린다. (분기가 달라지는 지점)
        for (int j = 0; j < q_size; j++) {
            string str = q.front();
            q.pop();

            for (int i = 0; i <= size_; i++) {
                string temp = str;
                reverse(temp.begin() + i, temp.begin() + i + K); // i번째 위치에서 k개 만큼 반대로 뒤집어준다.
                if (isAsc(temp)) return cnt; // 정렬되어 있다면 종료
                if (isTest.find(temp) == isTest.end()) { // 이미 테스트한 전적이 있는 항목은 더이상 테스트할 가치 X
                    isTest.insert(temp);
                    q.push(temp);
                }
            }
        }
    }
    // 끝가지 정렬이 되지 않는다면 -1 반환
    return -1;
}

int main() {
    q.push(input());
    if (isAsc(q.front())) { // 이미 정렬되어 있는 상태로 입력이 들어오면 끝.
        cout << 0;
        return 0;
    }
    cout << bfs() << endl;
    return 0;
}

---

🤔 문제 후기

사실 문제가 그렇게 어렵진 않았다. BFS의 정석인 문제였다. 오랜만의 알고리즘 문제 풀이라 BFS의 구현방식이 순간적으로 생각나지 않아서 몇 번 버벅거렸다. 가장 버벅거린 부분은 오름차순을 확인하는 메서드인 isAsc에서 int temp = str[i] - '0'; 부분이였는데, '0'을 빼주는 것을 까먹어서 한 10분 정도 원인을 몰랐던 것 같다. 그리고 reverse(temp.begin() + i, temp.begin() + i + K);에서도 뒤에 temp.begin() + i + K에서 +i+K가 아닌 +K를 했었는데, 이 부분도 찾는데 시간이 꽤 걸렸다... 예전에는 10분~20분 사이면 오류 없이 풀었던 것 같은데, 오랜만에 풀다 보니 1시간 가까이 걸렸던 것 같다.