P43163. 단어 변환

문제

제출 코드

• 사용 알고리즘 : BFS

각 단계별로 변환된 모든 단어를 큐에 담아서, 각 단어들에서 변환할 수 있는 모든 단어를 다시 담아 다음 단계로 넘기면 되는 문제.

주의할점은, 이미 만들어진 적이 있는 단어는 탐색할 필요가 없기에 방문체크를 해줘야 시간초과가 나지 않는다.

주어질 단어의 개수가 크지 않았기에, 완전탐색(BFS)로 충분히 풀 수 있었던 문제였다.

import java.util.*;

class Solution {

    static boolean checkChange(String target, String word){ // 한글자만 다른 단어인지 확인
        boolean result = false;
        int size = target.length();
        for(int i=0; i<size; i++){
            if(target.charAt(i)!=word.charAt(i)){
                if(result) return false;
                else result = true;
            }
        }
        return result;
    }

    static int changeWord(String begin, String target, String[] words){ // 단어 변환
        List<String> visit = new ArrayList<String>();
        Queue<String> queue = new LinkedList<String>();
        visit.add(begin);
        queue.add(begin);

        int depth = 0;
        while(!queue.isEmpty()){
            depth++;
            int size = queue.size();
            for(int i=0; i<size; i++){
                String now = queue.poll();

                for(String s : words){
                    if(!visit.contains(s) && checkChange(now, s)) {
                        if(s.equals(target)) return depth; // 목표 단어 도달
                        visit.add(s);
                        queue.add(s);
                    }
                }
            }
        }
        return 0;
    }

    public int solution(String begin, String target, String[] words) {

        return changeWord(begin, target, words);
    }
}