[알고리즘] 프로그래머스 단어 변환 :: 우유

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

프로그래머스

코드 설명

DFS를 최소한으로 돌아서 target 이랑 같아지는 경우를 확인하면 된다.

문자열에서 하나의 문자를 제외하고 나머지 문자열은 일치 해야하므로
k 에 문자열 -1이 저장되는 경우

        int k = 0;
        for (int j = 0; j < target.length(); j++) {
            if (begin.charAt(j) == words[i].charAt(j)) {
                k++;
            }
        }

방문 체크를 해주고 cnt + 1 을 해주면서 다시 DFS 한단계 더 깊게 들어가서 target이랑 일치하는 문자열이
나올때까지 확인해주면 된다.

            // 하나 빼고 다 일치하면
            if (k == target.length() - 1) {
                visited[i] = true;
                DFS(words[i], target, words, cnt + 1);
                visited[i] = false;
            }

 

전체 코드

class Solution {

    static int answer = 0;
    static boolean visited[];

    public int solution(String begin, String target, String[] words) {

        int words_cnt = words.length;
        visited = new boolean[words.length];


        DFS(begin, target, words, 0);


        return answer;
    }

    public void DFS(String begin, String target, String[] words, int cnt) {
        if (begin.equals(target)){
            answer = cnt;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            // 방문했으면 continue;
            if (visited[i])
                continue;

            int k = 0;
            for (int j = 0; j < target.length(); j++) {
                if (begin.charAt(j) == words[i].charAt(j)) {
                    k++;
                }
            }

            // 하나 빼고 다 일치하면
            if (k == target.length() - 1) {
                visited[i] = true;
                DFS(words[i], target, words, cnt + 1);
                visited[i] = false;
            }
        }
    }
}