🎯문제
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
입출력 예
| begin | target | words | return |
|---|---|---|---|
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
✏️풀이
코드
class Solution {
// 방문여부를 저장할 배열
static boolean[] visit;
static int answer;
// 깊이 탐색 메소드
public void dfs(String begin, String target, String[] words, int count) {
// 탐색된 값과 타겟이 동일할 경우
if(begin.equals(target)) {
// 탐색된 횟수를 저장된 answer와 비교하여 더 적은 값을 저장
answer = Math.min(count, answer);
return;
}
// words 배열의 길이만큼 반복문 설정
for(int i = 0; i < words.length; i++) {
// 방문여부를 확인하여 방문했다면 continue
if(visit[i]) {
continue;
}
// begin과 words가 동일한 단어인지 확인하기 위한 변수
int k = 0;
for(int j = 0; j < begin.length(); j++) {
if(begin.charAt(j) == words[i].charAt(j)) {
k++;
}
}
// 한글자만 다를 경우
if(k == begin.length() - 1) {
visit[i] = true;
dfs(words[i], target, words, count + 1);
visit[i] = false;
}
}
}
public int solution(String begin, String target, String[] words) {
answer = Integer.MAX_VALUE;
visit = new boolean[words.length];
// 탐색 시작
dfs(begin, target, words, 0);
return answer == Integer.MAX_VALUE ? 0 : answer;
}
}설명
dfs 탐색을 사용하여 진행하였다.
방문 여부를 저장할 visit 배열을 결과값을 저장할 int형 변수 answer를 선언한다.
dfs 메소드는 깊이 우선 탐색을 진행하는 메소드로 String begin, String target, String[] words, int count를 매개변수로 가진다. String형 변수 begin과 target은 각각 이전 탐색값과 최종 탐색을 해야하는 값을 뜻하며 String[] words는 문제에서 주어지는 배열이다. count는 탐색을 한 횟수이며, 이 탐색 횟수가 가장 적은 값이 이번 문제의 정답이 된다.
메소드의 구조를 살펴보면 탐색된 begin의 값과 target이 동일한 값일 경우 몇번째 탐색만에 target과 일치하게 되었는지 answer의 값과 비교를 진행하고 더 적은 값을 answer에 저장한다.
동일하지 않을 경우 계속 탐색을 진행한다. words 배열의 길이만큼 반복문을 진행하는데, 이때 방문을 했다면 continue를 사용해서 넘어가고 방문하지 않은 배열의 값들 중에서 탐색을 계속한다. begin과 words 배열의 값이 동일한 단어인지 확인하기 위해서 begin의 길이만큼 반복을 진행하여 한글자씩 비교한다. 이때 begin과 단 한글자만 다를 경우 탐색이 가능하므로 재귀호출을 사용하여 재탐색을 한다.
solution 메소드에서는 answer, visit의 초기화를 진행한다.
dfs 메소드를 호출하여 탐색을 진행하고 모든 탐색이 끝난 뒤 answer의 값을 확인한다. 이때 Integer.MAX_VALUE라는 초깃값이 그대로 있을 경우 0을 아니라면 answer에 저장된 값을 반환한다. 이렇게 하면 문제를 해결할 수 있다!
💡느낀 점
Level2에서 많이 풀었던 DFS 탐색 문제였다. 확실히 DFS 탐색에 대한 정리가 없이 문제를 풀었다면 많이 헤맸을 것 같다. 차근차근 준비하는 것의 중요성을 코테 준비를 하면서 깨닫고 있다.. 기본적인 틀은 비슷하지만 중간중간 과정이나 구조를 짤 때 약간씩은 다르기 때문에 문제를 풀 때 꼼꼼하게 읽어보면서 코드를 짜는 연습을 조금 더 열심히 해야겠다!
링크
DFS, BFS도 아직 많이 어렵네요ㅠㅠ 수고하셨어요!