[프로그래머스] 단어 변환

- dfs/bfs 

- 탈출 조건만 잘 잡는다고 생각하면 되었다.

 

import java.util.*;
class Solution {
    private int min;
    private void dfs(String cWord, int stage, String target, String[] words, boolean[] indexArr) {
        if(cWord.equals(target)) {
            if(min > stage) {
                min = stage;
            }
            return;
        }
        List<String> nWords = getOneDiffWords(cWord, words, indexArr);
        if(nWords.size() == 0) {
            return;
        }
        
        for(String nWord: nWords ) {
            int idx = Arrays.asList(words).indexOf(nWord);
            indexArr[idx] = true;
            dfs(nWord, stage+1, target, words, indexArr);
        }
    }
    
    private List<String> getOneDiffWords(String cWord, String[] words, boolean[] indexArr) {
        List<String> nWords = new ArrayList<>();
        for(int i=0; i<words.length; i++) {
            if(indexArr[i]) {
                continue;
            }
            String nWord = words[i];
            int count = 0;
            for(int j=0; j<nWord.length(); j++) {
                if(cWord.charAt(j) != nWord.charAt(j)) {
                    count++;
                }  
            }
            if(count == 1) {
                nWords.add(nWord);
            }
        }
        return nWords;
    }
    public int solution(String begin, String target, String[] words) {
        this.min = words.length + 1;
        boolean[] indexArr = new boolean[words.length];
        dfs(begin, 0, target, words, indexArr);
        return min == words.length + 1 ? 0 : min;
    }
}