C++로 문자열의 모든 회문 분할 출력하기

이 글에서는 주어진 문자열을 여러 조각으로 나누었을 때 모든 조각이 회문(palindrome)이 되도록 하는 모든 가능한 분할(partition)을 찾아 출력하는 방법을 다룹니다. 회문이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미합니다.

문제 이해하기

먼저 예시를 통해 문제를 살펴보겠습니다.

입력 − string = 'ababa'
출력 − ababa, a bab a, a b a b a …

'ababa'는 그 자체로 회문이므로 전체를 하나로 두는 것도 유효한 분할입니다. 또한 한 글자씩 잘라도 모든 조각이 회문이 되므로 역시 유효합니다. 이처럼 문자열을 다양하게 잘라 만들 수 있는 모든 조합을 찾아야 합니다.

해결 접근 방식

이 문제는 백트래킹(backtracking) 기법으로 효율적으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.

현재 위치에서 시작하는 부분 문자열(substring)이 회문인지 검사합니다.
회문이라면 현재 분할 목록에 추가하고, 남은 부분에 대해 재귀적으로 동일한 과정을 반복합니다.
재귀 호출이 종료되면 마지막에 추가한 조각을 제거(pop)하여 다른 경우의 수를 탐색합니다.
시작 위치가 문자열 길이에 도달하면 하나의 완성된 분할이 만들어진 것이므로 결과 목록에 저장합니다.

C++ 구현 코드

다음 프로그램은 위 접근 방식을 구현한 전체 예제입니다.

#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string str, int low, int high){
    while (low < high) {
        if (str[low] != str[high])
            return false;
        low++;
        high--;
    }
    return true;
}
void palindromePartition(vector<vector<string> >&allPart, vector<string> &currPart, int start, int n, string str){
    if (start >= n) {
        allPart.push_back(currPart);
        return;
    }
    for (int i=start; i<n; i++){
        if (isPalindrome(str, start, i)) {
            currPart.push_back(str.substr(start, i-start+1));
            palindromePartition(allPart, currPart, i+1, n, str);
            currPart.pop_back();
        }
    }
}
void generatePalindromePartitions(string str){
    int n = str.length();
    vector<vector<string> > partitions;
    vector<string> currPart;
    palindromePartition(partitions, currPart, 0, n, str);
    for (int i=0; i< partitions.size(); i++ ) {
        for (int j=0; j<partitions[i].size(); j++)
        cout<<partitions[i][j]<<" ";
        cout<<endl;
    }
}
int main() {
    string str = "abaaba";
    cout<<"Palindromic partitions are :\n";
    generatePalindromePartitions(str);
    return 0;
}

실행 결과

Palindromic partitions are :
a b a a b a
a b a aba
a b aa b a
a baab a
aba a b a
aba aba
abaaba

코드 동작 원리

1. isPalindrome() 함수

투 포인터(two-pointer) 기법을 사용합니다. 문자열의 양쪽 끝에서부터 문자를 하나씩 비교하며 중앙으로 이동하고, 단 하나라도 다른 문자가 발견되면 false를 반환합니다. 모든 비교가 통과하면 해당 부분 문자열은 회문입니다.

2. palindromePartition() 함수

재귀적으로 동작하는 백트래킹 함수입니다. start부터 i까지의 부분 문자열이 회문이면 currPart 벡터에 추가한 뒤, i+1 위치부터 다시 탐색을 이어갑니다. 탐색이 끝나면 pop_back()으로 마지막 조각을 제거하여 다음 분할 경우를 시도합니다. start가 n 이상이 되면 문자열 전체가 성공적으로 분할된 것이므로 allPart에 현재 결과를 저장합니다.

3. generatePalindromePartitions() 함수

전체 탐색 프로세스를 시작하고, 저장된 모든 분할 결과를 순회하며 화면에 출력하는 래퍼(wrapper) 함수입니다.

시간 복잡도

각 위치마다 회문 여부를 확인하면서 분기를 나누기 때문에 최악의 경우 시간 복잡도는 O(n × 2ⁿ)입니다. 공간 복잡도 역시 재귀 호출 스택과 결과 저장을 위해 O(n × 2ⁿ) 수준이 됩니다.

마무리

백트래킹을 활용하면 문자열의 모든 회문 분할을 체계적으로 찾을 수 있습니다. 이 패턴은 N-Queen 문제, 부분 집합 생성, 조합 탐색 등 다양한 알고리즘 문제에도 널리 응용되므로, 함께 학습해 두면 큰 도움이 됩니다.

C++로 문자열의 모든 회문 분할 출력하기 – 백트래킹 완벽 정리