[프로그래머스] 단어 변환 (JAVA)

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.

Code

import java.util.*;
class Solution {
    private int ret;
    private Map<String, List<String>> hm = new HashMap<>();
    public int solution(String begin, String target, String[] words) {
        ret = words.length+1;
        hm.put(begin, new ArrayList<>());
        // Begin Setting
        for(int i=0 ; i<words.length ; i++) {
        	hm.put(words[i], new ArrayList<>());
        	if(compare(begin, words[i])) {
        		hm.get(begin).add(words[i]);
        	}
        }        
        // Map Setting
        for(int i=0 ; i<words.length ; i++) {
        	for(int j=i+1 ; j<words.length ; j++) {
        		if(compare(words[i], words[j])) {
            		hm.get(words[i]).add(words[j]);
            		hm.get(words[j]).add(words[i]);
            	}
        	}
        }
        // DFS
        dfs(begin, target, new HashSet<String>(), 0, words.length);
        return ret>words.length?0:ret;
    }
    
    public boolean compare(String s1, String s2) {
		int cnt = 0;
		for(int i=0 ; i<s1.length(); i++) {
			char c1=s1.charAt(i), c2=s2.charAt(i);
			if(c1!=c2) {
				cnt++;
			}
			if(cnt>1) return false;
		}
		return true;
	}
    
    public void dfs(String s, String target, HashSet<String> hs, int cnt, int limit) {
		if(cnt>limit || cnt>ret) {
			return;
		}
		if(s.equals(target)) {
			ret = Math.min(ret, cnt);
			return;
		}
		for(String next : hm.get(s)) {
			if(hs.contains(next)) continue;
			hs.add(next);
			dfs(next, target, hs, cnt+1, limit);
			hs.remove(next);
		}
		return;
	}   
}