https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제

두 개의 단어 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 안에 없기 때문에 변환할 수 없습니다.

코드

import java.util.*;
class Solution {
    int answer = Integer.MAX_VALUE;
    int cnt = 0;
    
    public int solution(String begin, String target, String[] words) {
        List<String> list = Arrays.asList(words);
        if(!list.contains(target)){
            return 0;
        }
        boolean[] visited = new boolean[words.length];
        dfs(begin, target, words, visited, 0);
        return answer;
    }
    
    
    public void dfs(String begin, String target, String[] words, boolean[] visited, int cnt){
        if( begin.equals(target) ){
            answer =  Math.min(answer,cnt);
            return;
        }
        
        for(int i=0; i<words.length; i++){
            if(!visited[i] && diffCnt(begin, words[i])){
                visited[i] = true; 
                dfs(words[i], target, words, visited, cnt+1);
                visited[i] = false;
            }
        }
        
    }
    
    public boolean diffCnt(String str1, String str2){
        int diffcnt = 0;
        for(int i=0; i<str1.length(); i++){
                if(str1.charAt(i) != str2.charAt(i)){
                    diffcnt ++;
                }
            }
        return diffcnt ==1 ? true : false;
    }
}

풀이

한번 사용한 단어를 다시 사용하지 않게 하기 위해서 visited을 true로 바꿔줘야 하는 것과,
다른 루트로 가는 경우에는 사용할 수 있어야 하기 때문에 dfs 호출 후에 다시 false로 바꿔줘야 하는 부분을 생각하기 어려웠다. ㅠㅠ

DFS로 가능한 경우들을 구해서, 가장 최단 거리의 값을 Return 한다.
이 문제를 DFS로 풀기 적합한 근거는 ! 아래와 같다 (ChatGPT피셜..)

탐색 과정의 특성: 문제에서는 시작 단어 begin을 타겟 단어 target으로 변환하는 최소 단계 수를 구해야 합니다. 이는 탐색 과정에서 가능한 모든 경로를 탐색하고, 변환 단계 수가 최소인 경로를 찾는 문제입니다. DFS는 모든 가능한 경로를 탐색하는 데 적합한 알고리즘입니다.

깊이 우선 탐색: DFS는 현재 경로에서 더 이상 진행할 수 없을 때까지 가능한 한 깊이 탐색을 진행합니다. 주어진 문제에서도 시작 단어에서 한 글자씩 변환하며 탐색을 진행해야 하므로 깊이 우선 탐색이 적합합니다.

백트래킹: DFS는 백트래킹(backtracking)을 통해 이전 상태로 되돌아가며 다른 경로를 탐색할 수 있습니다. 주어진 문제에서도 한 번 방문한 단어는 다시 방문하지 않고, 이미 사용된 단어는 다른 경로에서 사용할 수 없어야 하므로 백트래킹이 필요합니다.

최소 단계 수 탐색: DFS를 사용하여 모든 가능한 경로를 탐색하면서 최소 단계 수를 갱신하면서 탐색하므로, 탐색이 완료된 후에는 최소 단계 수를 구할 수 있습니다.