프로그래머스 단어 변환2(JAVA)

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

프로그래머스

 

저는 bfs를 통해 문제를 해결하였습니다.

현재 단어에서 words에 있는 단어를 확인하고 현재 단어와 한 단어만 차이나면 bfs에 넣어 문제를 해결하였습니다.

 

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        Set<String> set = new HashSet<>();
        for(String word : words){
            set.add(word);
        }
        int answer = bfs(begin,target,set);
        return answer;
    }
    private int bfs(String begin,String end, Set<String> set){
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        visited.add(begin);
        q.offer(begin);
        int time = 0;
        int size = begin.length();
        while(!q.isEmpty()){
            int qSize = q.size();
            for(int s = 0 ; s < qSize ; s++){
                String now = q.poll();
                // System.out.println(time+" "+now);
                if(end.equals(now)){
                    return time;
                }

                for(String str : set){
                    int cnt = 0;
                    for(int i = 0 ; i < size ; i++){
                        if(str.charAt(i) != now.charAt(i)){
                            cnt++;
                        }
                    }
                    if(cnt == 1 && !visited.contains(str)){
                        q.offer(str);
                        visited.add(str);
                    }
                }
            }
            time++;
        }
        return 0;
    }
}