[Java 알고리즘] Word Ladder (글자 사다리) BFS 알고리즘.

문제 설명

시작 문자 : hit

끝 문자 : cog

문자 리스트 : hot, dot, dog, lot,log, cog

 

다음과 같이 parameter가 제공되고 시작 문자에서 한글자씩만 바꿔서 문자리스트에 있는 문자들을 통해 끝문자인 cog로 변경되는데까지의 횟수를 구하시오.

 

예를 들어, hit ->(ait..zit , hat..hzt , hia..hiz) -> hot -> dot -> dog -> log -> cog.    => 총 5회.

 

 

나의 풀이

class Main {
	public static void main(String[] args) {
        Main a = new Main();
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot","log", "cog");
        System.out.println(a.solve(beginWord, endWord, wordList));
    }
    
    public int solve(String beginWord, String endWord, List<String> wordList) {
        if(wordList == null || wordList.size() == 0) return 0;
        
        Queue<String> wordQueue = new LinkedList<>();
        wordQueue.offer(beginWord);
        int level = 1;
        
        while (!wordQueue.isEmpty()) {
            int size = wordQueue.size();
            for (int i = 0; i<size; i++) {
                String str = wordQueue.poll();
                if(str.equals(endWord)) return level;
                //get neighbor
                for (String neighbor : neighbors(str, wordList)) {
                    wordQueue.offer(neighbor);
                }
            }
            level++;
        }
        return 0;
    }
    
    public List<String> neighbors(String str, List<String> wordList) {
        
        List<String> result = new ArrayList<String>();
        Set<String> dict = new HashSet<String>(wordList);        
        
        for (int i = 0; i<str.length(); i++) {
            char[] chars = str.toCharArray();
            for (char ch = 'a'; ch <= 'z'; ch++) {
                chars[i] = ch;
                String s = new String(chars);
                if (dict.remove(s)) {
                   result.add(s); 
                }
            }
        }
        return result;
    }
}

wordQueue : 문자큐. 첫 대상은 beginWord(hit)이고 hit부터 한글자씩 변경하면서 wordList에 존재하는 값들을 담을 큐

Set을 사용하는 이유는 문자열의 중복을 제거하기 위함.

 

결국 요점은 hit 부터 알파벳이 하나씩 바뀌어가면서 wordList에 존재하는 값을 확인하고 큐에 넣어 이를 다시 알파벳을 변경하면서 중간중간 endWord와 비교해가면서 몇번의 for loop을 돌았는지 세면 된다.