프로그래머스 - 단어변환(DFS)

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

코딩테스트 연습 - 단어 변환

프로그래머스 단어변환입니다. DFS를 활용하여 풀 수 있습니다.

1. 단어를 변환할 수 있는 모든 경우의 수만큼 탐색을 진행합니다.

2. DFS의 종료 조건을 설정

3. DFS가 종료 조건을 달성했을 때, 달성까지 걸린 재귀의 횟수를 카운트( 재귀하는 만큼 단어의 변환 작업이 이루어 난 것)

4. 카운트 한 수중에서 가장 작은 값이 정답

package com.company;

import java.util.LinkedList;
import java.util.Queue;

public class 단어변환 {

    public static void main(String[] args){

        Solution solution = new Solution();
        solution.solution("hit", "cog" , new String[] {"hot","dot","dog","lot","log","cog"});


    }

    static class Solution {

        int max = 987654321;
        boolean[] visited;
        int diff = 0;
        public int solution(String begin, String target, String[] words) {

            visited = new boolean[words.length];

            DFS(begin, target, words, 0);

            if(max == 987654321)
                return 0;
            System.out.println(max);
            return max;
        }

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

            for(int i=0; i<words.length; i++){

                diff = 0;
                if(visited[i] == true) continue;

                for(int j=0; diff <= 1 &&j<begin.length(); j++){
                    if(begin.charAt(j) != words[i].charAt(j))
                        diff++;
                }

                if(diff == 1){
                    visited[i] = true;
                    cnt++;
                    DFS(words[i], target, words, cnt);
                    cnt--;
                    visited[i] = false;
                }


            }

        }

    }


}