단어 분리 문제(Word Break Problem) 개념과 C++ 구현 방법

단어 분리 문제는 공백 없이 이어져 있는 하나의 문장과, 유효한 영어 단어들로 구성된 사전이 주어졌을 때 해당 문장을 사전 속 개별 단어들로 나눌 수 있는 모든 가능한 방법을 찾는 알고리즘 문제입니다.

해결 방법은 문자열의 왼쪽부터 탐색을 시작하여 유효한 단어를 찾는 것입니다. 유효한 단어를 발견하면 그 단어 뒤에 남은 문자열 부분에서 다시 단어를 검색하는 과정을 재귀적으로 반복합니다.

입력 및 출력

입력:
유효한 단어들의 집합(사전)과, 여러 단어가 공백 없이 붙어 있는 문자열
사전: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream}
주어진 문자열: "ilovemangoicecream"
출력:
문자열을 주어진 단어들로 나누는 모든 가능한 방법
i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream

알고리즘

wordBreak(string, n, result)

입력 − 주어진 문자열, 문자열의 길이, 지금까지 분리된 문자열 결과.

출력 − 사전을 이용하여 분리된 문자열.

Begin
    for i := 0 to n, do
        subStr := 주어진 문자열의 (0..i) 범위 부분 문자열
        if subStr이 사전에 존재하면, then
            if i = n, then
                result := result + subStr
                결과 출력
                return
            wordBreak((i..n-i) 범위의 부분 문자열, n-i, result, subStr, '공백')
    done
End

이 알고리즘은 앞부분에서 잘라낸 부분 문자열이 사전에 존재하는지 확인하고, 존재한다면 나머지 문자열에 대해 같은 작업을 재귀적으로 수행합니다. 문자열 끝까지 도달하면 지금까지 누적된 결과를 출력함으로써 하나의 분리 방법을 완성합니다.

예제 코드

#include <iostream>
#define N 13
using namespace std;

string dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and",
                        "go","i","love","ice","cream"};

int isInDict(string word){      //단어가 사전에 존재하는지 확인하는 함수
    for (int i = 0; i < N; i++)
        if (dictionary[i].compare(word) == 0)
            return true;
    return false;
}

void wordBreak(string str, int n, string result) {
    for (int i=1; i<=n; i++) {
        string subStr = str.substr(0, i);       //문자열의 0번째부터 i번째 위치까지 추출
        if (isInDict(subStr)) {     //subStr이 사전에서 발견된 경우
            if (i == n) {
                result += subStr; //결과에 부분 문자열 추가
                cout << result << endl;
                return;
            }
            wordBreak(str.substr(i, n-i), n-i, result + subStr + " ");   //그렇지 않으면 나머지 부분을 다시 분리
        }
    }
}

int main() {
    string str="iloveicecreamandmango";
    wordBreak(str, str.size(),"");
}

실행 결과

i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream

위 실행 결과에서 볼 수 있듯이, 하나의 문자열이라도 사전에 포함된 단어 조합에 따라 여러 가지 방식으로 분리될 수 있습니다. 예를 들어 "man go"와 "mango"처럼 서로 다른 단어 조합이 동일한 원본 문자열을 만들어 내기 때문에, 이 문제는 가능한 모든 경우를 탐색하는 백트래킹 기반 재귀 기법으로 해결하는 것이 적합합니다.