programmers_단어 변환_java

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        if(isPossible(target, words)){ 
            boolean[] visited = new boolean[words.length];
            answer = bfs(begin, target, words, visited);
        }
        
        return answer;
    }
    
   	//target 여부
    public boolean isPossible(String target, String[] words){ 
        int size = words.length;
        for(int i = 0; i<size; i++){
            if(target.equals(words[i])){
                return true;
            }
        }
        return false;
    }
    
    // bfs 탐색
    public int bfs(String begin, String target, String[] words, boolean[] visited){
        Queue<String> queue = new LinkedList<>();
        queue.offer(begin);
        int cnt = 0;
        int size = words.length;
        while(!queue.isEmpty()){
            int queueSize = queue.size();
            
            for(int j = 0; j<queueSize; j++){
                String now = queue.poll();
                if(now.equals(target)){
                    return cnt;
                }
               
                for(int i = 0; i<size; i++){
                    if(!visited[i] && chageable(now, words[i])){
                        visited[i] = true;
                        queue.offer(words[i]);
                    }
                }
            }
            cnt++;
        }
        return 0;
    }
    
     // 변환 가능한 경우
    public boolean chageable(String word1, String word2){
        int size = word1.length();
        int cnt = 0;
        for(int i = 0; i<size; i++){
            if(word1.charAt(i) != word2.charAt(i)){
                cnt++;
            }
            if(cnt>1){
                return false;
            }
        }
        return true;
    }
}