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

🔗 단어 변환

import java.util.*;
class Solution {
    static boolean[] visited;
    static List<String> list;
    static Deque<String> queue;

    public int solution(String begin, String target, String[] words) {
        // 1. 한 번에 한 개의 알파벳 변경
        // 2. words 에 있는 단어로만 변경 

        // begin -> target 으로 가는데 최소 몇 단계의 과정을 거쳐야 하는지
        // 변환할 수 없는 경우는 0 return 


        // 단어 리스트
        list=new ArrayList<>(Arrays.asList(words));
        if(!list.contains(target)) return 0;

        // 번환된 단어 큐
        queue=new ArrayDeque<>();
        queue.add(begin); // 첫 단어 추가 

        // 방문 여부 배열
        visited=new boolean[words.length];

        // 최소 -> BFS
        return bfs(target,words);
    }
    private int bfs(String target,String []words){
        int answer =0;

        while(!queue.isEmpty()){
            int level=queue.size();
            answer++;

            // 단계마다 큐를 담기 위한 for문 
            for(int i=0;i<level;i++){
                String current=queue.poll();

                // 변환 가능한 단어를 찾고 큐에 추가
                for(int j=0;j<words.length;j++){

                    // 방문하지 않았고 변환가능하면
                    if(!visited[j] && canConvert(current,words[j])){

                        // target 과 같으면 변환이 완료된 것이므로
                        if(words[j].equals(target)) return answer;

                        // 방문 표시
                        visited[j]=true;

                        // 큐에 추가
                        queue.offer(words[j]);
                    }
                }

            }
        }
        return 0;
    }

    private boolean canConvert(String str1, String str2){
        int diffCnt=0;
        for (int i=0;i<str1.length();i++){
            // 같지 않은 횟수 세기
            if(str1.charAt(i)!=str2.charAt(i)) diffCnt++;
        }

        return diffCnt==1;
    }

}