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

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
	
	List<Integer> ans = new ArrayList<Integer>(); // target에 변환 도달 시 변환 횟수 저장 array
	
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        int[] visited = new int[words.length];
        DFS(words, begin, target, 0, visited);
        
        // 아무 곳에도 도달하지 못해 변환 불가능 한 경우
        if(ans.size()==0)
        	return 0;
        
        answer = Collections.min(ans);
        return answer;
    }
    
    void DFS(String[] words, String begin, String target, int cnt, int[] visited) {    	
    	// target에 도달한 경우 
    	if(checkDifferent(begin, target) == 0) {
    		ans.add(cnt);
    		return ;
    	}
    	
    	boolean chk = false;
    	for(int visit:visited) {
    		if(visit==0)
    			chk=true;
    	}
    	
    	// 더 이상 변환 불가능 할 경우
    	if(!chk || cnt > words.length) {
    		ans.add(0);
    		return;
    	}
    	
    	// 다음 변환값 찾기
    	for(int i = 0; i < words.length; i++) {
    		if(visited[i]==0 && checkDifferent(words[i], begin)==1) {
    			int[] tmp = visited.clone();
    			tmp[i]=1;
    			DFS(words, words[i], target, cnt+1, tmp);
    		}
    	}    		
    	return;
    }
    
    /*
     * 다른 글자 갯수 반환
     * */
    int checkDifferent(String word, String begin) {
    	String[] wordArr = word.split("");
    	String[] beginArr = begin.split("");
    	
    	int wordLength = wordArr.length;
    	int cnt = 0;
    	for(int i = 0; i < wordLength; i++) {
    		if(!wordArr[i].equals(beginArr[i])) {
    			cnt++;
    		}
    	}    	
    	return cnt;
    }
}

조건

단어 begin과 target이 존재하고, 단어의 집합 words가 존재한다.
한번에 한 개의 알파벳만 변환할 수 있고, words에 있는 단어로만 변환 가능하다.
begin에서 target으로 최소 몇단계를 거쳐서 변환 할수 있는지 구하며, 변환이 불가능할 경우 0을 반환한다.

풀이

1) checkDifferent 함수를 만들어 두 단어에서 다른 알파벳 수를 반환

• 0일때 동일하고,
• 1일때 changable하다.

2) DFS 함수를 통해

• target에 도달한 경우 변환 횟수를 저장하고
• 더이상 변환이 불가능 할 경우 0을 반환하고
• 다음 변환값을 찾아나간다.

어렵진 않은데,,, 중간에 왜 이렇게 막혔는지 모르겠다.
그래도 안 찾아보고 끝까지 풀어서 뿌듯하다.
다른 좋은 풀이도 또 찾아보자!