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

문제 설명 보기

>>programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

주어진 String 배열 안에서 진행 할 수 있는 Node가 한글자만 다른 String인 탐색 유형의 문제이다.

Queue를 사용한 BFS를 통해 해결했다.

 

import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        HashSet<String> isTraveled = new HashSet<>();
        LinkedList<String> nextStr = new LinkedList<>();

        nextStr.add(begin);

        while(!nextStr.isEmpty()){
            int size = nextStr.size();
            for(int i = 0; i < size; i++){
                String str = nextStr.pollFirst();
                if(str.equals(target)) return answer;
                for(String word : words){
                    int cnt = 0;
                    for(int idx = 0; idx < word.length(); idx++){
                        if(str.charAt(idx) == word.charAt(idx)){
                            cnt++;
                        }
                    }
                    if(cnt == str.length()-1 && !isTraveled.contains(word)){
                        isTraveled.add(word);
                        nextStr.add(word);
                    }
                }
            }
            answer++;
        }

        return 0;
    }
}