일단 시작해보는 블로그

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

CS/알고리즘 풀이

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

사용자 Selina Park 2020. 3. 11. 12:22

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

 

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

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog ->

programmers.co.kr

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;
        }
    }
}
0 Comments
댓글쓰기 폼