[Programmers] 모음사전(Lv.2)

풀이 소요시간 : 30분

진짜 기본중에 기본 백트래킹 문제인데 완전탐색이라는 유형이 주어지니까 오히려 이상한 뻘짓을 해버리는 바람에 시간을 많이 소요했다. 결국 모든 조합 순서를 구하는 문제이기에 별다른 접근방식은 없다.

다만 원하는 word 를 발견했을 때 탐색 자체를 종료하지는 않지만 전역변수 ans 를 바꿔서 값을 반환할 수 있다.

전체 코드

#include <string>
#include <vector>

using namespace std;


int ans, cnt;
char A[5] = {'A', 'E', 'I', 'O', 'U'};

void Dfs(string str, string word) {
    
    if(str == word)
    {
        ans = cnt;
        return;
    }
    
    if(str.length() == 5) 
    {
        return;
    }
    
    for(int i = 0; i < 5; i++)
    {
        cnt++;    
        Dfs(str + A[i], word);   
    }
}

int solution(string word) {
    string str = "";
    Dfs(str, word);
    return ans;
}