문제

해당 문제도 BFS 로 접근할 수 있겠지만 구현에 초점을 두었을 때 DFS를 통한 깊이우선탐색이 직관적이라 DFS 로 접근하였다

---

문제 접근

풀이에 앞서 미리 메모해가며 어떻게 풀 수 있는지 특이사항에 대해 기록하고 시작한다

1. 한번에 한개 글자 변경이 가능
2. words 안의 단어로만 변환 가능, words 의 길이는 모두 같으니 이는 고려하지 않아도 됨
3. begin 과 target 은 같지 않음
4. 변환할 수 없는 경우 0을 반환

이렇게 정의를 내리고 아래에는 대략적인 flow 를 기록한다

1. 유사성 검사를 실시하여 한개 글자만 바뀌는 경우 유망한 단어로 리스트에 담아준다
2. 현재 방문하지 않은 word 만 이 리스트에 담아준다
3. 깊이우선 탐색을 진행하고 재귀적으로 깊이를 늘려가면서 target 에 도달하면 반환한다
4. target 에 도달한다면 이전의 최소값과 비교하여 최소값을 업데이트한다
5. 최대 깊이 임에도 target 에 도달하지 않았다면 return

---

문제 풀이

1. static 전역 변수 지정하기

static String[] words;
static int minVal = Integer.MAX_VALUE;

• 최소값은 Int32 의 최대값으로 지정하여 최소값 업데이트를 보장한다
• words 를 전역변수로 두어 클래스 내에서 전역으로 사용

2. 유망한 단어를 찾는 메서드

public static List<Integer> getPossibleWord(String word, boolean[] visited){
        // 현재 word 에서 한개의 문자만 바뀌었을 때에 바뀔 수 있는 유망한 단어의 인덱스를 반환한다
        // 모든 단어의 길이는 같다
        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            int cnt = 0;
            if(!visited[i]){
                // 해당 단어로 바뀐 적이 없다면
                for (int j = 0; j < word.length(); j++) {
                    if(cnt > 1) break; // 두개이상의 문자가 차이나면 break
                    if(words[i].charAt(j) != word.charAt(j)) cnt++; // 문자가 다를때마다 +1
                }
                if(cnt==1) pos.add(i); // 만약 바뀔 수 있다면 pos 에 담아준다
            }
        }
        return pos;
    }

• 유망한 경우 해당 단어의 인덱스를 저장하여 준다
• 방문하지 않은 경우에만 유망한 경우를 탐색한다
• 한개 초과의 단어가 바뀌었을 때 break 하여 불필요한 탐색을 멈춤

3. DFS 함수

public static void dfs(String begin, String target, boolean[] visited, int cnt, int visitCnt){
        // 시작점이 현재 타겟과 같다면 현재 최대값과 비교 후 return;
        if(begin.equals(target)){
            minVal = Math.min(cnt, minVal);
            return;
        }
        if(visitCnt == visited.length) return;
        // 아니라면 유망한 경우를 찾는다
        List<Integer> pos = getPossibleWord(begin,visited);
        for (Integer p : pos) {
            visited[p] = true; // 해당 유망한 경우를 선택한 경우
            dfs(words[p], target, visited, cnt+1, visitCnt+1);
        }
    }

• visitCnt 를 통해 최대 깊이인지 확인한다
• begin 과 타겟이 같을 경우 최소값을 없데이트 후 반환

4. main 함수

public static void main(String[] args) {
        words = new String[]{"hot", "dot", "dog", "lot", "log"};
        boolean[] visited = new boolean[words.length];
        dfs("hit", "cog", visited, 0,0);

        if(minVal==Integer.MAX_VALUE) System.out.println(0);
        else System.out.println(minVal);
    }

---

전체 코드

import java.util.*;
class Solution {
    static String[] words;
    static int minVal = Integer.MAX_VALUE;

    public static List<Integer> getPossibleWord(String word, boolean[] visited){
        // 현재 word 에서 한개의 문자만 바뀌었을 때에 바뀔 수 있는 유망한 단어의 인덱스를 반환한다
        // 모든 단어의 길이는 같다
        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            int cnt = 0;
            if(!visited[i]){
                // 해당 단어로 바뀐 적이 없다면
                for (int j = 0; j < word.length(); j++) {
                    if(cnt > 1) break; // 두개이상의 문자가 차이나면 break
                    if(words[i].charAt(j) != word.charAt(j)) cnt++; // 문자가 다를때마다 +1
                }
                if(cnt==1) pos.add(i); // 만약 바뀔 수 있다면 pos 에 담아준다
            }
        }
        return pos;
    }
    
    public static void dfs(String begin, String target, boolean[] visited, int cnt, int visitCnt){
        // 시작점이 현재 타겟과 같다면 현재 최대값과 비교 후 return;
        if(begin.equals(target)){
            minVal = Math.min(cnt, minVal);
            return;
        }
        if(visitCnt == visited.length) return;
        // 아니라면 유망한 경우를 찾는다
        List<Integer> pos = getPossibleWord(begin,visited);
        for (Integer p : pos) {
            visited[p] = true; // 해당 유망한 경우를 선택한 경우
            dfs(words[p], target, visited, cnt+1, visitCnt+1);
            // visited[p] = false; // 백트래킹, 해당 유망한 경우를 선택하지 않은 경우
        }
    }
    
    public int solution(String begin, String target, String[] words1) {
        words = words1;
        boolean[] visited = new boolean[words.length];
        dfs(begin, target, visited, 0, 0);
        if(minVal == Integer.MAX_VALUE) return 0;
        return minVal;
    }
}