각 부분 문자열이 회문(Palindrome)이 되도록 문자열을 분할하는 방법의 수를 구하는 C++ 프로그램

이 글에서는 하나의 단어(문자열)를 여러 조각으로 나누되, 모든 조각이 회문(Palindrome)이 되도록 분할하는 방법이 총 몇 가지인지 구하는 C++ 프로그램을 살펴봅니다.

회문이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 뜻합니다. 예컨대 "tut", "o", "a"처럼 짧은 문자열도 회문에 해당합니다. 재귀 호출과 백트래킹을 활용하면 주어진 문자열에서 가능한 모든 회문 분할 조합을 체계적으로 탐색할 수 있습니다.

알고리즘

1. 단어를 입력으로 받습니다.
2. partitionadd 함수는 현재 위치(index)부터 한 글자씩 이어 붙여 임시 문자열 st를 만듭니다.
3. st가 회문이면 임시 목록 tmp에 추가하고, 아직 남은 문자가 있다면 다음 위치부터 재귀 호출로 탐색을 이어갑니다.
4. 문자열 끝에 도달하면 완성된 분할 하나를 결과 목록 u에 저장합니다.
5. partition 함수가 전체 탐색을 시작하며, 마지막에 printSol 함수가 저장된 모든 분할 결과를 화면에 출력합니다.

예제 코드

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

bool checkPalin(string s) { // 문자열이 회문인지 검사
    int length = s.length();
    length--;
    for (int i = 0; i < length; i++) {
        if (s[i] != s[length])
            return false;
        length--;
    }
    return true;
}

void printSol(vector<vector<string>> part) { // 분할 결과 출력
    for (int i = 0; i < part.size(); ++i) {
        for (int j = 0; j < part[i].size(); ++j)
            cout << part[i][j] << " ";
        cout << endl;
    }
    return;
}

void partitionadd(vector<vector<string>>& u, string& s, vector<string>& tmp, int index) {
    int length = s.length(); // 문자열 길이 저장
    string st;
    vector<string> curr = tmp;
    // 현재 문자열이 회문이면 추가하고, 남은 부분을 재귀적으로 분할
    if (index == 0)
        tmp.clear();
    for (int i = index; i < length; ++i) {
        st = st + s[i];
        if (checkPalin(st)) {
            tmp.push_back(st);
            if (i + 1 < length)
                partitionadd(u, s, tmp, i + 1);
            else
                u.push_back(tmp);
            tmp = curr;
        }
    }
    return;
}

// 'st'의 모든 회문 분할을 생성해 'u'에 저장
void partition(string st, vector<vector<string>>& u) {
    vector<string> tmp;
    partitionadd(u, st, tmp, 0);
    printSol(u);
    return;
}

int main() {
    string s = "tutorials";
    vector<vector<string>> part;
    cout << "the number of partitions:" << endl;
    partition(s, part);
    return 0;
}

실행 결과

the number of partitions:
t u t o r i a l s
tut o r i a l s

결과 해석

"tutorials"라는 단어는 두 가지 방식으로 회문 분할이 가능합니다.

• t u t o r i a l s — 모든 글자를 개별 조각으로 분리 (길이 1인 문자열은 항상 회문)
• tut o r i a l s — "tut"를 하나의 회문 조각으로 묶고 나머지는 개별 분리

따라서 이 단어를 각 조각이 모두 회문이 되도록 분할하는 방법은 총 2가지입니다.