코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환

이전 코드

import java.util.*;

class Solution {
    int answer = 0;
    public int solution(String begin, String target, String[] words) {
        boolean isFind = false;
        answer = words.length + 1;
        
        for (String word : words){
            if (word.equals(target)){
                isFind = true;
                break;
            }
        }
        if (!isFind){
            return 0;
        }
        
        dfs (begin, begin, new ArrayList<>(Arrays.asList(words)), 0,  target);

        return answer;
    }
    
    public void dfs (String pastWord, String currentWord, ArrayList <String> wordsArrayList, int node, String target){
        if (currentWord.equals(target)){
            answer = Math.min(answer, node);
        } else {

            ArrayList<String> wordArrayList = new ArrayList<>();
            wordArrayList.addAll(wordsArrayList);
            wordArrayList.remove(pastWord);

            for (int i = 0; i < wordArrayList.size(); i++) {
                if (isChange(currentWord, wordArrayList.get(i))) {
                    dfs(currentWord, wordArrayList.get(i), wordArrayList, node + 1, target);
                }
            }
        }
    }
    
    public boolean isChange(String st1, String st2){
        int count = 0;
        for (int i = 0 ; i < st1.length() ; i++){
            if(st1.charAt(i) != st2.charAt(i)){
                count ++;
                if(count > 1){
                    return false;
                }
            }
        }
        return true;
    }
}

최근 코드

import java.util.*;

class Solution {
    int answer;
    public int solution(String begin, String target, String[] words) {
        answer = words.length + 1;
        ArrayList <String> arrayList = new ArrayList<>(Arrays.asList(words));
        if (!arrayList.contains(target)){
            return 0;
        }
        searchWord(begin, begin, target, arrayList, 0);
        return answer;
    }
    
    public void searchWord(String past, String current, String target, ArrayList<String> arrayList, int count){
        if (current.equals(target)){
            answer = Math.min(answer, count);
        } else {
            ArrayList<String> wordArrayList = new ArrayList<>();
            wordArrayList.addAll(arrayList);
            wordArrayList.remove(past);
            for (String word : wordArrayList){
                if (isChange(current, word)){
                    searchWord(current, word, target, wordArrayList, count + 1);
                }
            }
        }
    }
    
    public boolean isChange(String s1, String s2){
        int count = 0;
        for (int i = 0 ; i < s1.length() ; i++){
            if (s1.charAt(i) != s2.charAt(i)){
                if (++count > 1){
                    return false;
                }
            }
        }
        return true;
    }
}