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

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 

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

---

 

풀이

모든 경우들을 dfs로 탐색해가며 만약 현재단어가 target과 같다면 answer값을 갱신시켜주었다.

탐색하는 방법은

1. 현재 단어와 탐색하지 않은 단어들을 비교한다.

2. 1개를 제외한 알파벳이 같은 단어가 있다면, 해당 단어를 탐색했다는 체크를 해준뒤, 현재 단어로 갱신시켜준다.

3. 갱신된 현재 단어로 1~2번을 반복한뒤, 해당 단어를 탐색했다는 체크를 해제해준다.

 

코드

class Solution {
    static boolean visited[]=new boolean[50];
    static int answer=99;
    public void dfs(String now,String target,int cnt,String[] words){
         if(now.equals(target)){
             answer=Math.min(answer,cnt);
             return;
         }
        
        for(int i=0;i<words.length;i++){
            if(visited[i]) continue;
            int c=0;
            String t=words[i];
            for(int j=0;j<t.length();j++){
                if(now.charAt(j)==t.charAt(j)) c++;
            }
            if(c==t.length()-1){
                visited[i]=true;
                dfs(t,target,cnt+1,words);
                visited[i]=false;
            }
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        dfs(begin,target,0,words);
        answer=(answer==99)?0:answer;
        return answer;
    }
}