[Programmers]#Level2_모음 사전, 완전 탐색, DFS(깊이 우선 탐색)

 

[Programmers 알고리즘, C++]#Level 2_모음 사전

 

Programmers 알고리즘 문제 풀이, Level2_모음 사전

DFS를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

#2. 풀이

1. DFS(깊이 우선 탐색)

[자료구조]#6_그래프

 

• [정의] : 깊이 우선 탐색은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다. 깊이 우선 탐색은 시작 노드로부터 출발해 노드를 추가하며 더 이상 확장 할 수 없는 최대 깊이까지 우선적으로 탐색하는 방법입니다.
• [방법] : 일반적으로, DFS를 구현하는 방법은 "재귀 함수"와 "스택"을 사용해 구현할 수 있습니다. 

 

2. 깊이 우선 탐색 조건 설정

1. 먼저, DFS는 재귀 함수를 통해 구현할 수 있으며, 재귀 함수는 불만족 조건을 우선적으로 작성해야 합니다. 만약, 문자열의 최대길이에 도달하거나, 목표 문자열과 동일한 문자열이 구성되었을 경우 함수를 종료합니다.
2. 다음으로, DFS의 시작 문자열을 빈 문자열로 시작해 목표 문자열에 도달하는데 필요한 탐색 횟수를 결과 값으로 반환합니다.

 

#3. 코드

#include <string>
#include <vector>

using namespace std;

int answer = 0;
int cnt = -1;
string target = "";
string aeiou = "AEIOU";

// #1. 깊이 우선 탐색 : target 문자열이 완성되기 전까지 "AEIOU"중 한 문자를 이어붙여가며 재귀적으로 검사
void dfs(string str)
{
    cnt++;
    
    if(str == target)
    {
        answer = cnt;
        return;
    }
    
    if(str.length() >= 5) return;
    
    for(int i=0; i<5; i++)
        dfs(str + aeiou[i]);
}

int solution(string word) {

    target = word;
    
    dfs("");
    
    return answer;
}