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

DFS 연습

 

 - 탈출 조건 (= target 단어를 맞췄을 경우 && 최소 단계 확인)

 - 단어 변경 메소드 시 (check로 이미 flag가 true 인지 확인)

 

 

주의점

 - 한 단어 차이가 나는 단어가 복수 개 일 수 있음(조건 한번 더 잘 생각할 것!)

 

import java.util.*;
class Solution {
    int min;
    String target;
    String[] words;
    boolean[] checkWords;
    
    private void dfs(String cWord, int stage) {
        if(cWord.equals(target)) {
            if(min > stage || min == 0) {
                min = stage;
            }
            return;
        }
        
        List<Integer> indexArr = findOneDiff(cWord);
        
        if(indexArr.size() == 0) {
            return;
        }
        
        for(Integer index: indexArr) {
            checkWords[index] = true;
            dfs(words[index], stage + 1);
            checkWords[index] = false;
        }
    }
    
    private List<Integer> findOneDiff(String cWord) {
        List<Integer> result = new ArrayList<>();
        
        for(int i=0;i<words.length;i++) {
            int diff = 0;
            if( checkWords[i] ) {
                continue;
            }
            
            String baseWord = words[i];
            for(int j=0;j<cWord.length(); j++) {
                if(baseWord.charAt(j) != cWord.charAt(j)) {
                    diff++;
                }   
            }
            if(diff == 1) {
                result.add(i);
            }
        }
        return result;
    }
    
    public int solution(String begin, String target, String[] words) {
        min = 0;
        this.words = words;
        this.target = target;
        checkWords = new boolean[words.length];
        dfs(begin, 0);
        return min;
    }
}