프로그래머스 DFS/BFS 단어변환

재귀함수가 확실히 생각을 많이 해야되는 것 같다. 봐도 이해가 잘 안되네...

다른 사람것 참고!

// dfs 함수 내에서 탐색할 단어와 target단어가 같다면
	// 최소변환 과정을 업데이트 시켜줘야함 (BFS에서는 이 과정이 필요가 없음)
    // 리턴한다.
// words 배열을 탐색한다.
	// 해당 idx를 방문하지 않았다면
    	//탐색할 단어와 target단어를 비교하면서 '한개의 알파벳만 다른지' 확인한다.
		//한개의 알파벳만 다르다면
        	//해당 idx를 방문표시한다.
            //해당 단어를 가지고 dfs함수를 부른다.
            //방문표시를 해제한다. (재귀함수에서 리턴이 되었다는 것은, 이전단계로 돌아왔다는 것이며, 이는 해당 idx를 방문하지 않음을 의미하기 때문에 방문표시를 해제한다.)

class Solution {
	// 방문 확인을 위한 배열
	static boolean[] visited; 
    static int answer = 0;
	
    
	public int solution(String begin, String target, String[] words) {
    	// words에 들어있는 단어들을 전부 탐색하고 방문 표시를 할 것이기 때문에
        visited = new boolean[words.length];
        
        dfs(begin, target, words, 0);
        return answer;
    }
    
    
    public static void dfs(String begin, String target, String[] words, int count) {
    	// 재귀함수를 계속해서 하다가 시작점과 target과 일치하는 경우 중지
    	if (begin.equals(target)) { 
        	answer = count;
            return;
        }
        
        for (int i = 0; i < words.length: i++) { // words배열의 단어들을 전부 탐색
			// 이미 사용한 단어면 넘어가고 아니면 진행
            if (visited[i]) continue; 
            
            int sameSpell = 0; // 같은 스펠링이 몇개인지 세기
            for (int j = 0; j < begin.length(); j++) { 
            	// begin의 글자와 words의 원소 글자가 동일하면 증가
            	if (begin.charAt(j) == words[i].charAt(j)) sameSpell++;
            }
            
            if (sameSpell == begin.length() - 1) { // 한글자 빼고 모두 같은 경우
            	visited[i] = true;
                dfs(words[i], target, words, count + 1);
                visited[i] = false;
            }
        }
    }
}

참조

https://velog.io/@like02_like0/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Programmers-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98-DFS-%ED%92%80%EC%9D%B4-%EC%9E%90%EB%B0%94-JAVA-zjqy756m