백트래킹으로 문자열의 모든 순열 출력하기

문자열 순열 문제란?

주어진 문자열의 모든 순열(permutation)을 출력하는 문제는 백트래킹(Backtracking) 기법을 설명할 때 가장 널리 사용되는 대표적인 예제입니다. 이 방식은 탐색 범위인 부분 문자열의 크기를 한 단계씩 줄여가며 하위 문제를 해결하고, 해결이 끝나면 이전 상태로 되돌아가(백트래킹) 같은 구간에서 또 다른 순열을 만들어 내는 방식으로 동작합니다.

예를 들어 문자열이 ABC라면 만들 수 있는 모든 순열은 다음과 같습니다.

ABC, ACB, BAC, BCA, CAB, CBA

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n!)으로 매우 큽니다. 길이가 n인 문자열에서 가능한 순열의 개수 자체가 n!개이기 때문입니다. 따라서 문자열 길이가 조금만 늘어나도 실행 시간이 급격히 증가하므로, 학습용 예제나 짧은 문자열 처리에 적합하다는 점을 유의해야 합니다.

입력 및 출력 형식

입력: 문자열 "ABC"

출력: ABC의 모든 순열
ABC
ACB
BAC
BCA
CBA
CAB

알고리즘: stringPermutation(str, left, right)

입력: 문자열 str과 탐색 범위를 나타내는 left, right 인덱스

출력: 문자열의 모든 순열을 화면에 출력

Begin
    if left = right, then                      // 더 이상 교환할 위치가 없다면
        display str                            // 하나의 순열이 완성 → 출력
    else
        for i := left to right, do
            swap str[left] and str[i]              // left 위치와 i 위치의 문자를 교환
            stringPermutation(str, left+1, right)  // 다음 위치에 대해 재귀 호출
            swap str[left] and str[i]              // 원상복구 (백트래킹)
        done
End

동작 원리 살펴보기

핵심 아이디어는 단순합니다. 왼쪽부터 한 글자씩 자리를 고정해 나가는 방식입니다.

첫 번째 위치에 올 문자를 정하기 위해 left 위치의 문자와 i번째 문자를 서로 교환(swap)합니다.
첫 글자가 고정된 상태에서 나머지 부분 문자열에 대해 같은 과정을 재귀적으로 반복합니다.
재귀 호출이 끝나면 반드시 스왑을 되돌려(원상복구) 원래 상태로 복원합니다. 이 단계가 바로 백트래킹이며, 생략하면 이후 교환 순서가 어긋나 잘못된 결과가 나오게 됩니다.

C++ 구현 예제

#include<iostream>
using namespace std;

void stringPermutation(string str, int left, int right) {
    if(left == right)
        cout << str << endl;
    else {
        for(int i = left; i<= right; i++) {
            swap(str[left], str[i]);
            stringPermutation(str, left + 1, right);
            swap(str[left], str[i]); // 백트래킹을 위한 원상복구
        }
    }
}

int main() {
    string str = "ABC";
    cout << "All permutations of " << str << " is: " << endl << endl;
    stringPermutation(str, 0, str.size()-1);
}

실행 결과

All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB

마무리 정리

이 문제의 핵심은 '선택 → 탐색 → 선택 취소'라는 백트래킹의 기본 패턴을 익히는 것입니다. 재귀 호출 후 스왑을 되돌리는 원상복구 과정이 있어야 모든 경우의 수를 빠짐없이, 그리고 올바른 순서로 탐색할 수 있습니다. 참고로 C++에서는 표준 라이브러리의 std::next_permutation 함수를 사용하면 직접 구현하지 않고도 사전순 순열을 손쉽게 생성할 수 있습니다.

백트래킹으로 문자열의 모든 순열 출력하기 – 원리와 C++ 구현