단어 목록이 주어졌을 때, 재귀(recursion) 기법을 활용하여 각 목록에서 단어를 하나씩 선택함으로써 만들 수 있는 모든 가능한 문장을 생성하는 것이 이 글의 목표입니다. 이때 각 목록에서는 한 번에 한 단어씩만 가져올 수 있습니다.
입출력 시나리오 살펴보기
입력 −
sentence[row][col] = {{"I", "You"},
{"Do", "like"},
{"walking", "eating"}}
출력 −
I Do walking I Do eating I like walking I like eating You Do walking You Do eating You like walking You like eating
설명 − sentence[0~2]의 각 목록에서 한 단어씩 가져와 위와 같은 문장들을 만들 수 있습니다.
입력 −
sentence[row][col] = {{"work", "live"},{"easy", "happily"}}
출력 −
work easy work happily live easy live happily
설명 − sentence[0~1]의 각 목록에서 한 단어씩 가져와 위와 같은 문장들을 만들 수 있습니다.
알고리즘 단계
문자열 타입의 2차원 배열 sentence[row][col]을 선언한 후, Recursive_Print(sentence) 함수에 데이터를 전달합니다.
Recursive_Print(sentence) 함수 내부에서는 다음을 수행합니다.
문자열 타입의 배열 arr[row]를 생성합니다.
i가 0부터 col 미만까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 sentence[0][i]가 비어 있지 않으면 Recursion(sentence, 0, i, arr) 함수를 호출합니다.
Recursion(string sentence[row][col], int temp_1, int temp_2, string arr[row]) 함수 내부에서는 다음을 수행합니다.
arr[temp_1]을 sentence[temp_1][temp_2] 값으로 설정합니다.
temp_1이 row - 1과 같은지 확인합니다. 같다면 i가 0부터 row 미만까지 반복하는 FOR 루프를 시작하고, 루프 안에서 arr[i]를 출력한 후 반환합니다.
i가 0부터 col 미만까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 sentence[temp_1+1][i]가 빈 문자열이 아니면 Recursion(sentence, temp_1+1, i, arr) 함수를 재귀적으로 호출합니다.
결과를 출력합니다.
예제 프로그램의 접근 방식
아래 프로그램은 위 알고리즘을 그대로 구현한 것입니다. 먼저 첫 번째 행의 각 단어에 대해 재귀 호출을 시작하고, 마지막 행에 도달할 때마다 지금까지 선택된 단어들로 하나의 완성된 문장을 출력합니다. 이 과정을 통해 모든 조합을 빠짐없이 탐색할 수 있습니다.
예제
#include<bits/stdc++.h>
#define row 3
#define col 3
using namespace std;
void Recursion(string sentence[row][col], int temp_1, int temp_2, string arr[row]){
arr[temp_1] = sentence[temp_1][temp_2];
if(temp_1 == row - 1){
for(int i=0; i < row; i++){
cout << arr[i] << " ";
}
cout << endl;
return;
}
for(int i=0; i < col; i++){
if(sentence[temp_1+1][i] != ""){
Recursion(sentence, temp_1+1, i, arr);
}
}
}
void Recursive_Print(string sentence[row][col]){
string arr[row];
for(int i=0; i < col; i++){
if(sentence[0][i] != ""){
Recursion(sentence, 0, i, arr);
}
}
}
int main(){
string sentence[row][col] = {{"Ajay", "sanjay"},{"Like", "is"},{"Reading", "eating"}};
Recursive_Print(sentence);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Ajay Like Reading Ajay Like eating Ajay is Reading Ajay is eating sanjay Like Reading sanjay Like eating sanjay is Reading sanjay is eating
이처럼 재귀 함수를 활용하면 각 행에서 단어를 하나씩 조합하는 모든 경우의 수를 체계적으로 탐색할 수 있습니다. 다만 생성되는 문장의 수는 각 행의 단어 개수에 따라 지수적으로 증가하므로, 행이나 열의 크기가 커질수록 실행 시간이 크게 늘어난다는 점을 유의해야 합니다.