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

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

---

풀이

class Solution {
    
    static int count;
    static boolean[] visited;
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        count = Integer.MAX_VALUE;
        visited = new boolean[words.length];
        dfs(begin, target, 0, words);
        if(count != Integer.MAX_VALUE){
            answer = count;
        }
        return answer;
    }

    public void dfs(String begin, String target, int depth, String[] words){
        if(begin.equals(target)){
            count = Math.min(count, depth);
            System.out.println(count);
            return;
        }

        for(int i = 0; i < words.length; i++){
            if(!visited[i] && checkChange(begin, words[i])){
                visited[i] = true;
                dfs(words[i], target, depth+1, words);
                visited[i] = false;
            }
        }
    }

    public boolean checkChange(String begin, String change){
        int num = 0;
        for(int i =0 ; i < begin.length(); i++){
            if(begin.charAt(i) == change.charAt(i)){
                num++;
            }

        }

        if(num == begin.length() -1){
            return true;
        }else{
            return false;
        }
    }
}

 

방문 확인을 위한 visited배열을 선언해주고 전역변수 count를 최대 정수값으로 초기화해준다. 이는 작은 정수를 찾기 위함이다.

 

dfs에 들어간다. 시작 단어와 목표 단어, 깊이, 단어 배열을 매개변수로 갖는다.

 

만약 시작 단어가 목표 단어와 같다면 그때의 depth를 count와 비교해 더 작은 것을 저장한다.(여기서 변하면서 깊어지는 것임을 생각해서 depth-1을 하는 것이 아닌 depth를 그대로 쓰면 된다.)(이런 부분에 항상 주의하자)

 

그렇지 않다면 인덱스 0번부터 비교가 시작된다. 방문한 적이 없고, 변환 가능한 단어라면(1개 차이) 변환 한 것으로 dfs를 진행하며 백트래킹으로 조합적인 부분도 확인한다.