Word Ladder

프로그래머스에도 존재하는 좋은 문제이다. 내가 생각보다 자바가 이제 꽤 익숙하게 사용하는거 같아서 기분이 좋다. 물론 Stream() 같은 부분이 아직까지도 헷갈리는 부분이지만 계속 연습하다보면은 나아질거 같은기분이다. 이 문제는 beginWord가 주어지고 최소한의 경로로 endWord까지 가야한다. 이때 좀 고민을 했던게 visited 배열을 사용하면서 bfs탐색을 해야하나 생각했지만 그냥 Map을 visited 배열처럼 사용해도 문제 없이 풀 수 있었다.

자바를 사용하면서 C++와 크게 다르다고 생각했던 부분 중 하나는 Struct 와 Pair 이다. C++에서는 Struct와 Pair을 적절히 사용하면서 굉장히 유용하고 빠르게 코드를 작성했는데 자바에서는 그런게 없다보니 그냥 class 를 하나 새로 만들어주는게 훨씬 속편하다. HashMap만 적절히 사용할 수 있다면 정말 무난하게 풀 수 있는 BFS문제였다.

class Solution {
    public class Count{
        public String word; 
        public int count; 
        public Count(String word, int count){
            this.word = word;  
            this.count = count; 
        }
    }
    public boolean findDiff(String curr, String compare){
        int cnt = 0; 
        for(int i = 0; i < curr.length(); i++){
            if(curr.charAt(i) != compare.charAt(i)) cnt++; 
            if(cnt > 1) return false; 
        }
        return true; 
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String,Integer> hashMap = new HashMap<>(); 
        Queue<Count> queue = new LinkedList<>(); 
        for(String s : wordList){
            hashMap.put(s,0); 
        }
        if(!hashMap.containsKey(endWord)) return 0; 
        queue.add(new Count(beginWord,1)); 
        while(!queue.isEmpty()){
            int size = queue.size(); 
            for(int i = 0; i < size; i++){
                Count first = queue.poll(); 
                String curr = first.word; 
                int dist = first.count; 
                
                if(curr.equals(endWord)) return dist; 
                
                for(String ss : wordList){
                    if(hashMap.get(ss) != 1 && findDiff(curr,ss)){
                        hashMap.put(ss,1); 
                        queue.add(new Count(ss,dist+1)); 
                    }
                }
            }
        }
        return 0; 
    }
}