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

 

BFS

import java.util.*;
class Solution {
    static boolean visited[];
    public int solution(String begin, String target, String[] words) {
        Queue<String> q = new LinkedList<>();
        q.offer(begin);
        int count = 0;
        visited = new boolean[words.length];
        
        boolean has = false;
        for (String w : words) if (w.equals(target)) { has = true; break; }
        if (!has) return 0;
        
        while(!q.isEmpty()){
            int size = q.size();
            for(int k=0;k<size;k++){
                String cur = q.poll();
                if(cur.equals(target)) return count;
           
                for(int i=0;i<words.length;i++){
                    if(visited[i]) continue;
                    int cnt = 0;
                    for(int j=0;j<cur.length();j++){
                        if(cur.charAt(j) != words[i].charAt(j))cnt++;
                    }
                    if(cnt == 1){
                        visited[i] = true;
                        q.offer(words[i]);
                    }
                }   
            }
            
            count++;
        }
        
        return count;
    }
    
}

 

 

DFS

class Solution {
    static int answer = Integer.MAX_VALUE;
    static boolean visited[];
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        
        dfs(begin, target, words, 0);
        if(answer == Integer.MAX_VALUE) return 0;
        return answer;
    }
    static void dfs(String begin, String target, String[] words, int count){
        if(begin.equals(target)) {
            answer = Math.min(answer, count);
            return;
        } else {
            
        boolean flag = false;
        for(int i=0;i<words.length;i++){
            if(visited[i]) continue;
            int cnt = 0;
            for(int j=0;j<begin.length();j++){
                if(begin.charAt(j) != words[i].charAt(j)) cnt++;
            }
            if(cnt == 1){
                if(visited[i]) return;
                visited[i] = true;
                dfs(words[i], target, words, count+1);
                visited[i] = false;
            }
        }
            
        }
       

    }
}