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

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

프로그래머스

 

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

BFS를 통해 begin부터 target까지 갈 수 있는지를 확인하였습니다.

words에 있는 것만으로 단어를 변환해야 하므로, 현재 문자열과 words의 단어들과 비교하여 하나만 다르다면 해당 단어로 진행할 수 있도록 구현하였습니다.

 

package Programmers.ETC;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class 단어_변환 {
    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();
                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;
    }
}