[pro] 프로그래머스 level3 43163 단어 변환 (Java) - DFS

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

[풀이]

words 배열을 돌면서 기존 단어 중 알파벳 하나만 바뀌어서 words 배열 안에 있는 단어로 변환 가능하다면, 변환 후 dfs를 다시 호출한다.

dfs는 단어가 target 단어와 일치하면 count를 반환한다.

 

[코드]

 

import java.util.*;
class Solution {
    boolean[] visited;
    int ans = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        // 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 
    
        visited = new boolean[words.length];
        if(!Arrays.asList(words).contains(target)){
            return 0;
        }
        else{
            dfs(begin, target, 0, words);
            answer = ans;
        }
        
        return answer;
    }
    
    public void dfs(String word, String target, int count, String[] words){
        if(word.equals(target)){
            ans = Math.min(count, ans);
        }
        
        for(int i=0; i<words.length; i++){
            if(visited[i]) continue;
            
            if(canChange(word, words[i])){
                visited[i] = true;
                dfs(words[i], target, count+1, words);
                
                visited[i] = false;
            }
        }
        return;
    }
    
    public boolean canChange(String word, String w){
        int cnt = 0;
        for(int i=0; i<word.length(); i++){
            if(word.charAt(i)!=w.charAt(i))
                cnt++;
            if(cnt>1){
                return false;
            }
        }
        return true;
    }

}