[알고리즘_풀이] 프로그래머스 - 단어변환 java

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

코딩테스트 연습 - 단어 변환 | 프로그래머스

import java.util.*;

class Solution {
	public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        HashMap<String, Node> map = new HashMap<>();
        
        for(int i=0; i<words.length; i++) {
            Node in = new Node();
            map.put(words[i], in);
        }        
        
        map.put(begin, new Node());
        answer = dfs(begin, target, words, map);
        
        return answer;
    }

    public int dfs(String begin, String target, String[] words, HashMap<String, Node> map) {
        // target이 words에 포함되지 않으면 리턴
        if(map.containsKey(target) == false) {
            return 0;
        }
                
        Stack<String> stack = new Stack<>();
        stack.push(begin);
        int count = Integer.MAX_VALUE;
        
        while(!stack.isEmpty()) {
            String out = stack.pop();
            map.get(out).checked = true;

            if(out.equals(target)) {
                count = Math.min(count, map.get(out).count);
            }
            // 한 알파벳만 다른 word List 가져오기
            stack = getWords(out, words, map, stack, map.get(out).count);
        }
        return count;
    }

    public Stack<String> getWords(String key, String[] words, HashMap<String, Node> map, Stack<String> stack, int parent_count) {
        int wordLength = key.length();
        
        for(String w: words) {
            if(map.get(w).checked == false) {
				int count = 0;
                for(int i=0; i<wordLength; i++) {
                    if(w.charAt(i) != key.charAt(i)) {
                        count++;
                    }
                }
                if(count == 1) {
                    map.get(w).count = parent_count + 1;
                    stack.add(w);
                }
            }
        }
        
        return stack;
    }

    class Node {
        int count;
        boolean checked;
        Node() {
            this.count = 0;
            this.checked = false;
        }
    }
}