99클럽 코테 스터디 7일차 TIL + 완전탐색(C++)

코드

#include <string>
#include <vector>
using namespace std;

vector<char> vowels = {'A', 'E', 'I', 'O', 'U'};
int cnt = 0;  // 현재까지 몇 번째 단어인지 저장하는 변수
int ans = 0; // 목표 단어의 순서를 저장하는 변수
string target; // 찾고자 하는 단어

void dfs(string current) {
    // 현재 단어가 목표 단어와 같다면 결과 변수에 순서를 저장하고 종료
    if (current == target) {
        ans = cnt;
        return;
    }

    // 단어의 길이가 5이면 더 이상 탐색하지 않음
    if (current.size() == 5) return;

    // 다음 알파벳을 추가하면서 DFS 탐색
    for (char vowel : vowels) {
        cnt++;  // 새로운 단어가 생성될 때마다 순서를 증가
        dfs(current + vowel);  // 재귀 호출로 다음 문자 추가
        if (ans != 0) return;  // 이미 결과를 찾았으면 빠져나옴
    }
}

int solution(string word) {
    target = word;
    dfs("");  // 빈 문자열부터 시작하여 DFS로 단어 생성
    return ans;
}

 

풀이

문제에서 단어들은 다음과 같은 순서로 사전에 저장된다.

A
AA
AAA
AAAA

AAAAA
AAAAE
AAAAI
AAAAO
AAAAU

AAAE
AAAEA
AAAEE
AAAEI
AAAEO
AAAEU

AAAI
AAAIA
AAAIE
AAAII
AAAIO
AAAIU

...

이는 A부터 시작해 A, E, I, O, U의 모음들을 하나씩 더해가며 DFS로 재귀호출하여 생성한 문자열들과 같다.

따라서, target단어가 몇번째 단어인지 알아내기 위해 DFS을 사용하여 재귀호출 하는 방식으로 빈 문자열에서 단어를 생성해나간다. 이때 새로운 단어를 생성할 때마다 cnt를 증가시킨다.

문자열이 target과 일치하면 ans에 cnt를 저장하고 리턴한다.

 

회고

처음에 어떤 식으로 푸는지 감이 안 잡혀서 구글링해서 DFS 라는 힌트를 보고 풀었다. 다른 사람의 풀이를 보니 상수를 사용해 푼 풀이도 있는데, 완전탐색은 어떤 식으로 접근해야할지 처음에 감이 안 잡혀서 어려운 것 같다… 연관된 문제를 많이 풀어봐야할 것 같다.