프로그래머스 - 단어변환

전형적인 bfs,dfs알고리즘 문제이다. 둘 중 아무 방식으로 사용해도 될 것 같다. (보통 bfs로 많이 푸신다.

import java.util.*;

class Solution {
    int ans = Integer.MAX_VALUE;
    
    public int solution(String begin, String target, String[] words) {
        
        if ( !Arrays.stream(words).anyMatch(target::equals))
            return 0;
        
        boolean[] check = new boolean[words.length];
        
        dfs(begin,target,words,check,0);
           
        return ans;
    }
    
    public void dfs(String current, String target,String[] words,boolean[] check,int depth) {
        
        if (current.equals(target) || depth>=words.length) {
            ans = Math.min(ans,depth);
            return;
        }
        
        
        for (int i=0;i<words.length;i++) { 
            
            if (!check[i] && changeCheck(current,words[i])) {
                check[i]=true;
                dfs( words[i],  target, words, check,depth+1);
                check[i]=false;
            }
        }
    }

    public boolean changeCheck(String first, String second) {
        int count =0;
        for (int i=0;i<first.length();i++) {
            if (first.charAt(i) != second.charAt(i)) {
                count++;
            }
        }
        return count == 1 ;
        
    }
    
}

dfs방식으로 풀었다. 반복문으로 푸는 것이 더 좋지만 재귀 함수로 풀어 보았다.
풀고 나니 다른 분들은 Node클래스를 만들어 푸셨는데 훨씬 효율적인 코드였다.

출처 : 프로그래머스 알고리즘