프로그래머스 '단어 변환' 자바

썸머코딩이 끝난 후 일단 가장 많이 나오는 DFS/BFS 부터 정복하자는 생각으로 풀게 되었다

 

접근 방법

BFS와 DFS 중 고민했는데 DFS로 해서 재귀함수로 하는게 최솟값을 찾는게 더 편하겠다고 생각이 들었다

begin 부터 words의 0번째 배열부터 탐색을 시작해서 1개 빼고 다 같으면 다시 그 단어부터 찾는 방식이다

미리 방문을 표기할 수 있는 배열 visited와 최솟값 변수인 temp를 전역 변수로 선언해 dfs 메소드 내에서도 

사용하게 했다. 

 

package codingtestStudy;

import java.util.*;

public class wordTransformation {
    static boolean[] visited;
    static int temp;
    public static void main(String[] args) {
        int a = solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"});
        System.out.println(a);
    }

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

    static void dfs(String begin, String target, String[] words, int depth) {
        if(begin.equals(target) && temp > depth){
            temp = depth;
        }
        int count;
        for(int i = 0; i < words.length; i++){
                count = 0;
                if(visited[i] == true){
                    continue;
                }
            for(int j = 0; j < begin.length(); j++){
                if(words[i].charAt(j)==begin.charAt(j)){
                    count++;
                }
            }
            if(count == begin.length()-1){
                visited[i] = true;
                dfs(words[i], target, words, depth+1);
            }
            visited[i] = false;
        }
    }


}