모든 Permutation case 출력하기 문제는 전형적인 backtracking을 이용하는 문제다. 이 문제의 해설과 함께 backtracking에 대해 살펴보자.

문제

입력으로 자연수 $n$이 주어졌을때, $1$부터 $n$까지 모든 수가 한 번씩 들어가도록 문자열을 구성하는 경우를 모두 출력하시오.

입력

자연수 $n$이 입력으로 주어진다.

출력

$1$부터 $n$까지 모든 수가 한 번씩 들어가는 문자열의 모든 경우가 한 줄씩 출력된다. (단, 순서는 고려하지 않는다.)

예시

입력

3

출력

123
132
213
231
312
321

---

백트래킹(Backtracking)이 뭔가요?

백트래킹은 해를 찾다가 더 이상 탐색할 길이 없으면 다시 뒤로 돌아가는 문제해결 알고리즘이다.

나는 다음과 같은 방식으로 문제를 해결했다.

1. 예시의 출력결과를 보고 규칙을 찾는다.
   123 → 132, 213 → 231, 312→321에서 뒤의 두 자리를 서로 바꾸는 규칙이 있고, 123, 213, 321이 원래의 문자열 123에서 첫번째 원소와 다른 원소들을 서로 바꾼 모양이라는 규칙을 찾았다.
2. 해당 규칙에 맞게 알고리즘을 작성한다.
   재귀적으로 swap을 계속하면 될 것 같아 재귀를 이용하여 문자열을 출력하고 나면 이전 단계로 돌아가도록 코드를 작성했다.

코드

아래는 해당 문제를 해결한 코드다.

#include <iostream>

template <class T>
void swap(T &a, T &b) {
    T temp = a;
    a = b;
    b = temp;
}

void print(int seq[], int n) {
    for(int i=0; i<n; i++)
        std::cout << seq[i];
}

void permute(int seq[], int start, int end, int n) {
    if (start == end) {
        print(seq, n);
        puts("");
    }
    else {
        for (int i = start; i <= end; i++) {
            swap(seq[start], seq[i]); // swap
            permute(seq, start + 1, end, n); // permutation of rest string
            swap(seq[start], seq[i]); // for backtracking
        }
    }
}

void permutNumbers(int n) {
    int arr[n];
    for (int i=1; i <= n; i++) {
        arr[i-1] = i;
    }
    permute(arr, 0, n-1, n);
}

int main() {
    int n;
    std::cin >> n;
    permutNumbers(n);
}

추가적인 관점

이 문제는 완전그래프 H(n)의 모든 노드를 지나는 경로의 경우의 수를 모두 출력하는 문제로 일반화 할 수 있다.

레퍼런스

1. https://leetcode.com/problems/permutations/

2. https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/