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

출처 : hj-bank.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F

TISTORY

 

풀이 

1. dfs 사용 ( words의 길이가 최개 50이므로 O(n^2) = 2500 이므로 ㄱㅊ

2. begin 으로부터 words를 모두 참조하며 한 알파벳 변경으로 가능한지 체크

3. 가능한 곳을 모두 들어가보며 바뀐 문자열이 target과 같은지 체크하자.

4. 모두 검사했는데 아니라면 visited=  false 통해서 완전 탐색 실시

5. 그 중 count값이 가장 작은거 출력

코드

import java.util.*;

class Solution {
    
    static boolean[] visited ; 
    static ArrayList<String> word ;
    static int answer;
    public int solution(String begin, String target, String[] words) {
        answer = Integer.MAX_VALUE;
        word = new ArrayList<>();
        visited = new boolean[words.length];
        
        for( int i=0; i<words.length; i++){
            word.add(words[i]);
        }
        
        if ( !word.contains(target)) return 0;
        
        // 1. begin 으로부터 가능한 words 모두 담기
        dfs(begin, 0, 0, target);
        // 2.          
        return answer;
    }
    private static void dfs(String begin, int idx, int count, String target){
        // 발견하면 끝
        if ( begin.equals(target)){
            answer = Math.min(count, answer);
            return;
        }
        
        // idx 끝나면 끝
        if( idx == word.size() ){

            return;
        }
        
        for( int i=0; i<word.size(); i++){
            
            // 한 개의 알파벳만 변경 가능한지 && 방문하지 않았는지
            if( Isonechange(begin, i) && !visited[i] ){
                visited[i] = true;
                dfs( word.get(i), idx+1, count+1,target);                
                visited[i] = false;
            }
            
        }
        
    }
    private static boolean Isonechange(String begin, int idx ){
        int cnt = 0;
        // 한 단어만 바꿀 수 있는지 체크
        for( int i=0; i<begin.length(); i++){
            if( begin.charAt(i) != word.get(idx).charAt(i) ) cnt ++;
        }
        if ( cnt == 1) return true;
        else return false;
        
    }
}