취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11268번 문제인 Bell Ringing이다.
문제는 아래 링크를 확인하자.

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

Steinhaus-Johnson-Trotter Algorithm은 인접한 원소 한 쌍의 swap만으로 다음 순열을 생성하는 방식으로 모든 순열을 정확히 한 번씩 생성하는 알고리즘이다. 이 알고리즘의 다음 원소 생성 방식은 문제에 주어진 연산의 제약 내에서 항상 실행 가능하므로 해당 알고리즘의 순열생성방식을 따라 모든 순열을 출력하는 것으로 문제를 충분히 해결할 수 있다.

Steinhaus-Johnson-Trotter Algorithm은 브루트포스 및 순열과 조합을 공부할 때 한번쯤 봤을 법한 기초 알고리즘이므로 이것이 가장 쉬운 풀이가 아닐까 한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<string> vec[9];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vec[1].emplace_back("1");
    for (int i = 2; i < 9; i++) {
        char c = ('0' + i);
        int sgn = 1;
        for (auto &x:vec[i - 1]) {
            if (sgn) {
                for (int len = i - 1; len >= 0; len--) {
                    string tmp = x.substr(0, len);
                    tmp += c;
                    tmp += x.substr(len, i - 1 - len);
                    vec[i].emplace_back(tmp);
                }
            }
            else {
                for (int len = 0; len < i; len++) {
                    string tmp = x.substr(0, len);
                    tmp += c;
                    tmp += x.substr(len, i - 1 - len);
                    vec[i].emplace_back(tmp);
                }
            }
            sgn ^= 1;
        }
    }
    cin >> N;
    for (auto &s:vec[N]) {
        for (auto &l:s) cout << l << ' ';
        cout << '\n';
    }
}