[프로그래머스] 43163 단어 변환

문제

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

풀이

begin과, words에서 문자 1개가 차이나는 문자열을 찾으며 DFS로 들어간다.
이때 dfs를 들어가기 전에 vistied[i] = true 하고, dfs를 나오면 visited[i] = false 로 복구하며 모든 경우를 탐색한다
if(begin.equals(target)) 라면 answer = cnt 를 통해 문자열 words에서 target이 없을 시 0을 반환하게 한다.

dfs내에서, word를 돌면서 해당 word가 방문한 word라면 넘어가고 방문하지 않은 word라면 현재 begin과 한글자씩 비교하여 다른 경우 check++
check가 1이라면 고려하고 있는 해당 단어가 한 번 바뀌었다는 의미이므로 words[i]와 cnt+1를 가지고 dfs로 들어간다.

코드

/**
* DFS(begin, target, words, cnt) // cnt 증가하는 것 조심
* dfs 종료 조건 : begin(word[i])과 target이 같은 경우
* dfs(
        word를 돌면서 방문한 word라면 넘어가고 방문하지 않은 word라면
        현재 begin과 한글자씩 비교하여 다른 경우 check++
        
        check == 1 (즉 한 글자만 바뀌었다면)
        visited[i] = true
        그 다음 단어 탐색하기 위해 dfs 진입
        dfs 빠져나오면 visited[i] = false
    )
    
DFS 다 돌았는데도 target과 같아지지 않았다면 초기화한 answer = 0 그대로 결과가 됨
*
**/

class Solution {
    
    boolean[] visited; // word 에 대한 visited
    int answer;
    
    public int solution(String begin, String target, String[] words) {
        answer = 0;
        visited = new boolean[words.length];
        
        DFS(begin, target, words, 0);
        return answer;
    }
    
    public void DFS(String begin, String target, String[] words, int cnt){
        
        // return 조건
        if(begin.equals(target)){
            answer = cnt;
            return;
        }
        
        for(int i=0; i<words.length; i++){
            
            if(visited[i] == true){
                continue; // 방문한 곳이라면 패스
            }
            
            int check = 0;
            
            // begin과 바꾸려는 words의 i번째 단어와 비교
            for(int j=0; j<begin.length(); j++){
                if(begin.charAt(j) != words[i].charAt(j)){
                    check++;
                }
            }
            
            if(check == 1){
                // 한 번 바뀌었다면
                visited[i] = true;
                DFS(words[i], target, words, cnt+1);
                visited[i] = false;
            }
        }
    }
}