오늘의 학습내용
- 완전탐색
- dfs
공부한 내용
DFS는 가능한 한 깊게 탐색한 후, 더 이상 깊게 갈 수 없으면 다음 경로로 이동하는 방식으로 작동한다.
DFS의 주요 특징과 동작 방식은 다음과 같다:
주요 특징
- 깊이 우선: 먼저 최대한 깊이 탐색한다. 즉, 현재 노드에서 갈 수 있는 가장 먼 노드까지 탐색한 후 돌아온다.
- 재귀적 또는 스택 사용: DFS는 재귀적으로 구현할 수 있으며 비재귀적 구현에서는 명시적인 스택을 사용한다.
- 그래프 탐색: 트리뿐만 아니라, 순환(cycles)이 있을 수 있는 그래프에서도 사용된다.
동작 방식
- 시작 노드를 스택(또는 재귀 호출 스택)에 넣는다.
- 스택에서 노드를 꺼내어 방문한다.
- 방문한 노드와 연결된 모든 인접 노드들을 스택에 넣는다.
- 스택이 비어 있을 때까지 2번과 3번 과정을 반복한다.
DFS의 응용
- 경로 찾기: 시작점에서 목표 지점까지의 경로를 찾을 때 사용된다.
- 사이클 검출: 그래프 내에서 순환(cycle)이 있는지 확인할 때 유용하다.
- 위상 정렬: DAG(Directed Acyclic Graph)에서의 위상 정렬을 수행할 때 사용된다.
- 연결 요소 찾기: 그래프의 연결 요소들을 식별하는 데 사용된다.
오늘의 회고
오늘의 문항은 한 분기점을 선택한후 그 곳에서 가능한 깊게 들어가는 방식이기 때문에 dfs라고 할 수 있겠다. 따라서 재귀적인 호출을 이용하여 dfs를 구현하였다.
문제
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- word의 길이는 1 이상 5 이하입니다.
- word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
내 풀이
import java.util.*;
class Solution {
private static String[] vowels = {"A", "E", "I", "O", "U"};
private static ArrayList<String> list;
public static int solution(String word){
int answer = 0;
list = new ArrayList<>();
dfs("", 0);
int size = list.size();
for(int i=0; i<size; i++){
if(list.get(i).equals(word)){
answer = i;
break;
}
}
return answer;
}
public static void dfs(String word, int len){
list.add(word);
if(len == 5) return;
for(int i=0; i<5; i++){
dfs(word + vowels[i], len+1);
}
}
}다른 사람 풀이
무조건 dfs로 구현한 내 풀이와는 달리 어떤 사람은 아예 수학적으로 접근한 풀이도 있었다. 이런 방식도 존재한다는 것을 알아두자.
class Solution {
public int solution(String word) {
int answer = 0, per = 3905;
for(String s : word.split("")) answer += "AEIOU".indexOf(s) * (per /= 5) + 1;
return answer;
}
}