[알고리즘] 프로그래머스 - 단어변환 (dfs/bfs)

1. 문제

2. 문제풀이

현재 주어진 단어를 한글자씩 수정해서 최종 목표 단어로 변환이 가능한지를 구하고, 만약 변환이 가능하다면 몇번만에 가능한지 최소 변환 횟수를 구하는 문제였다. 

 

현재 단어에서 words 배열에 있는 단어로 변환이 가능하다면 visit 배열에 방문을했다고 표시를 한 후 dfs 탐색 방법을 이용해서 탐색을 진행한다. dfs의 base case로는 전부 방문했거나, 현재 단어와 찾는 단어가 같을 경우 탐색을 종료했다. 그리고 최소 횟수를 계속 갱신하여 최종적으로 minNum을 반환한다. 변환이 불가능할 경우 0을 반환한다.

class Solution {
    
    int minNum = 999999999;
    
    public void dfs(boolean[] visit, String[] words, String word, String target, int depth){
    
        if(isAllVisit(visit) == true)
            return;
        
        if(word.equals(target)){
            if(depth < minNum)
                minNum = depth;
            return;
        }
        
        int len = words.length;
        for(int i=0;i<len;i++){
            
            if(visit[i] == true)
                continue;
            
            if(isChngAble(word, words[i])){
                visit[i] = true;
                dfs(visit, words, words[i], target, depth+1);
                visit[i] = false;
            }
        }
    }
    
    public boolean isAllVisit(boolean[] visit){
        boolean isAllVisit = false;
        int len = visit.length;
        
        for(int i=0;i<len;i++){
            if(visit[i] == false)
                return false;  
        }
        
        return isAllVisit;
    }
    
    public boolean isChngAble(String word, String targetWord){
        boolean isChngAble = false;
        int sameCharNum = 0;
        int len = word.length();
        for(int i=0;i<len;i++){
            if(word.charAt(i) == targetWord.charAt(i))
                sameCharNum++;
        }
        
        if(len-1 == sameCharNum)
            isChngAble=true;
        
        return isChngAble;
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        boolean[] visit = new boolean[words.length];
        
        dfs(visit, words, begin, target, 0);
        
        if(minNum == 999999999){
            return 0;
        } else {
            return minNum;
        }
    }
}