Backtracking | Write a program to print all permutations of a given string

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
• 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

주어진 문자열의 모든 순열 출력

'Permutation(순열)'이란 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산을 말한다. 그러므로 주어진 집합 S에 대해 정의역과 공역이 같은 일대일 연산이다.

길이 $n$ 문자열이 주어졌을 때 전체 순열 출력의 시간 복잡도

생성할 수 있는 문자열의 개수는 $n!$개이나 $n$길이 문자열 출력에 걸리는 시간이 $O(n)$이므로 전체 시간 복잡도는 $O(n\cdot n!)$이다.

재귀트리 예제와 코드

python 코드

def toString(List): 
    return ''.join(List) 

def permute(a, l, r): 
    if l==r: # 치환 시작점과 끝 점이 동일하면 탐색이 끝났음을 의미하므로
        print toString(a) # 문자열 출력
    else: 
        for i in range(l,r+1): # l부터 r까지 반복
            a[l], a[i] = a[i], a[l] # l과 i인덱스 값 교체
            permute(a, l+1, r) # l+1로 시작점 옮긴 뒤 재귀 호출
            a[l], a[i] = a[i], a[l] # backtrack과정으로 원상복구를 의미
string = "ABC"
n = len(string) 
a = list(string) 
permute(a, 0, n-1) 

C++ 코드

#include <bits/stdc++.h> 
using namespace std; 

void permute(string a, int l, int r)  
{   
    if (l == r)  
        cout<<a<<endl; // 탐색 깊이가 끝까지 도달하면 출력
    else
    {    
        for (int i = l; i <= r; i++) // 입력받은 범위에 대해
        {   
            swap(a[l], a[i]); // l 주소와 i 주소에 할당된 값 교체
            permute(a, l+1, r); // 재귀 호출로 시작점을 옮겨 더 깊이 탐색
            swap(a[l], a[i]); // backtracking한 뒤 다음 단계 진행
        }  
    }  
}  

int main()  
{  
    string str = "ABC";  
    int n = str.size();  
    permute(str, 0, n-1);  
    return 0;  
}  

C 코드

#include <stdio.h> 
#include <string.h> 

void swap(char *x, char *y) 
{ // x, y는 입력받은 주소값이 가르키는 알파벳 문자
    char temp; // 값을 중간에 보관할 버퍼 선언
    temp = *x; // 버퍼에 x 주소가 가르키는 값 저장
    *x = *y; // x 주소에 y 주소가 가르키는 값 저장
    *y = temp; // y 주소에 버퍼가 저장했던 값 저장
} 
// 중간에 x, y를 출력하면 메모리가 담고 있는 값은 문자 전체이므로
// 주소값이 가르키는 문자열부터 메모리가 갖는 문자열의 끝 부분까지 출력됨
void permute(char *a, int l, int r) 
{ 
   int i; 
   if (l == r) 
     printf("%s\n", a); // 깊이가 끝까지 도달하면 출력
   else
   { 
       for (i = l; i <= r; i++) //  
       { 
          swap((a+l), (a+i)); // 'A'의 주소값에매개변수를 더한 뒤 호출
          permute(a, l+1, r); // 재귀 호출로 시작점을 옮겨 더 깊이 탐색
          swap((a+l), (a+i)); // backtracking한 뒤 다음 단계 진행
       } // 주의점: 영어는 1byte라 주소값에 매개변수를 더해 접근하였음
   } // 한글은 byte 단위가 다르므로 조정해야 한다.
} 

int main() 
{ 
    char str[] = "ABC"; // str은 'A'에 할당된 주소값을 갖는다.
    int n = strlen(str); 
    permute(str, 0, n-1); 
    return 0; 
} 

OUTPUT

ABC
ACB
BAC
BCA
CBA
CAB

위 코드들은 조건을 필터링하는 코드가 없으므로 반복되는 문자열이 존재하면 동일한 순열을 출력한다. (중복 허용)

Backtracking은 조건에 맞는 '모든' 경우의 수를 탐색하는 과정이므로 특정 단계를 수행 후 더 깊은 단계에서의 탐색을 위해 재귀 호출한 다음 끝까지 도달하면 재귀문을 빠져나와 원상복구하여 옆 단계로 진행한다. 그래서 위 코드들 처럼 swap, permute swap이 반복된다.

앞으로 포스팅되는 문제들을 해결하면서 Backtracking 구현의 숙달을 목표로 한다. 개인적으로 코딩 테스트에 단골로 나오는 해결법 중 하나이다. small case 문제가 주어진 경우 도저히 해법이 생각이 나지 않을 때 쓰는 필살기같은 알고리즘이다. 시간 복잡도가 엄청나게 나오겠지만 문제 조건에 맞는지 검사하여 더 깊이 탐색하지 않도록 코드를 작성하면 오히려 탐색 시간이 훨씬 줄어드는 경우가 있다.

참고자료

1. Write a program to print all permutations of a given string