C# 역추적(Backtracking) 알고리즘으로 문자열의 모든 순열 구하기

역추적(Backtracking) 기법은 첫 번째 위치의 문자를 고정하고, 나머지 문자들을 첫 번째 문자와 차례로 교환(swap)하는 방식으로 모든 순열을 탐색합니다.

예를 들어 "ABC"라는 문자열이 있다면, 첫 번째 반복에서 A를 A, B, C와 각각 교환하여 ABC, BAC, CBA 세 가지 문자열이 생성됩니다.

이후 두 번째 문자 B를 고정하는 방식으로 나머지 문자들에 대해서도 동일한 과정을 반복합니다. 각 단계가 끝날 때마다 다시 스왑하여 이전 상태로 되돌아가는 역추적 작업을 수행하는 것이 핵심입니다.

예를 들어 ABC에서 두 번째 위치에 B를 고정해 ABC를 만든 뒤, 이전 위치로 역추적하고 B를 C와 교환하면 ACB를 얻을 수 있습니다. 이러한 방식으로 최종적으로 ABC와 ACB 두 순열이 완성됩니다.

예제 코드

using System;
namespace ConsoleApplication{
    public class BackTracking{
        public void StringPermutation(string word, int start, int end){
            if (start == end){
                Console.WriteLine(word);
            }
            else{
                for (int i = start; i <= end; i++){
                    Swap(ref word, start, i);
                    StringPermutation(word, start + 1, end);
                    Swap(ref word, start, i);
                }
            }
        }
        private void Swap(ref string word, int start, int end){
            char[] arr = word.ToCharArray();
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            word = new string(arr);
        }
    }
    class Program{
        static void Main(string[] args){
            BackTracking b = new BackTracking();
            b.StringPermutation("ABC", 0, 2);
        }
    }
}

실행 결과

ABC
ACB
BAC
BCA
CBA
CAB

코드 설명

StringPermutation 메서드는 시작 인덱스(start)와 끝 인덱스(end)가 같아지면 하나의 순열이 완성된 것이므로 해당 문자열을 출력합니다. 그렇지 않은 경우에는 for 루프를 돌며 현재 위치의 문자를 각 인덱스의 문자와 교환한 뒤 재귀 호출로 다음 위치를 탐색하고, 호출이 끝나면 다시 원래대로 되돌려 놓습니다.

Swap 메서드는 C#의 문자열이 불변(immutable)이라는 특성 때문에 문자열을 char 배열로 변환한 후 두 위치의 문자를 교환하고, 다시 새로운 문자열로 만들어 반환하는 역할을 담당합니다.