게하! 개하! (게임도 하고 개발도 하고)

[프로그래머스] 단어 변환 - java 본문

알고리즘/[2021] 프로그래머스

[프로그래머스] 단어 변환 - java

Sorrel 2021. 6. 1. 01:13
class Solution {
    static int sum_count = Integer.MAX_VALUE; //최솟값을 찾기 위한 count
    void dfs(boolean[] visited, String target, String[] words, String begin, int count){
        
        //target 이라면 count가 sum_count보다 작으면 갱신해줌
        if(begin.equals(target)){
            if(sum_count>count){
                sum_count=count;
            }
            return ;
        }
        
        for(int i = 0; i<words.length; i++){
            if(!visited[i]&&check(begin, words[i])){
                visited[i]=true;//중요, 무한루프에 빠질 가능성 없애줌
                dfs(visited, target, words, words[i], count+1);
                visited[i]=false;
            }
        }
    }
    //한글자만 바뀌는지 체크하는 함수
    public boolean check(String str1, String str2){
        int num =0;
        for(int i =0; i<str1.length(); i++){
            if(str1.charAt(i)!=str2.charAt(i)){
                num++;
            }
        }
        if(num==1){
            return true;
        }
        return false;
    }
    //메인함수
    public int solution(String begin, String target, String[] words) {
        
        dfs(new boolean[words.length],target, words, begin, 0);
        if(sum_count == Integer.MAX_VALUE){
            return 0;
        }
        
        return sum_count;
    }
}
0 Comments
댓글쓰기 폼
Prev 1 2 3 4 5 6 7 8 Next