[프로그래머스](깊이우선) 단어 변환

단어 변환

조건
1. 한번에 한개의 알파벳만 바꿀수 있음
2. word의 단어로만 변환할수 있음
3. 각 단어는 알파벳 소문자로만 이루어져 있습니다.
4. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
5. words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
6. begin과 target은 같지 않습니다.
7. 변환할 수 없는 경우에는 0를 return 합니다.

풀이 방법
1. 시작으로 주어진 단어를 바탕으로 character를 한개씩 변환해가면서 target을 찾는다.
2. dfs로 words에 있는 단어들을 한개씩 비교 하는 방식이다.
3. 시작되는 단어와 words list의 단어 중 character 한개가 다른것이 있으면, count+1을 하여 그 단어를 다시 시작단어로 하여 처음부터 words list와 비교한다.
5. 이렇게 비교하다가 target과 같은 단어가 나올때 answer값에 count값을 저장한다.
6. dfs로 비교하다가 count 값이 이전에 저장한 answer 값 작을때(최소값이 될 수 있는 값) answer의 값을 더 작은 count로 바꿔서 저장 한다.
7. 변환할수 없는경우 0으로 나와야 하므로, 처음에 answer값을 Integer Max값으로 저장해놓고, 마지막에 answer값이 그대로이면 0으로 출력한다.

package test;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class test11 {

    public static int answer = Integer.MAX_VALUE;

    public static boolean check(String begin, String target) {

        int c = 0;
        for (int i = 0; i < begin.length(); i++) {
            if (begin.charAt(i) != target.charAt(i)) {
                c++;
            }
        }
        Integer.MAX_VALUE

        return c == 1 ? true : false;

    }

    public static void dfs(String[] sa, String begin, String target, int count, boolean used[]) {
        if (begin.equals(target)) {
            answer = (answer > count) ? count : answer;
            return;
        }

        for (int i = 0; i < sa.length; i++) {
            if (!used[i]) {
                if (check(begin, sa[i]) == true) {
                    used[i] = true;
                    dfs(sa, sa[i], target, count + 1, used);
                    used[i] = false;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("src/test11.txt"))));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        String begin = st.nextToken();
        String target = st.nextToken();

        st = new StringTokenizer(br.readLine());
        int count = Integer.parseInt(st.nextToken());

        String[] sa = new String[count];
        for (int i = 0; i < count; i++) {
            String word = br.readLine();
            sa[i] = word;
        }

        boolean used[] = new boolean[count];

        dfs(sa, begin, target, 0, used);

        System.out.println(answer);

    }
}