[Java/프로그래머스/DFS] Level 3: 단어 변환

문제

programmers.co.kr/learn/courses/30/lessons/43163

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

 

코드

처음 문제를 봤을 때 DFS로 풀 생각도 하지 못했다...ㅎ

 

풀이 순서는,

1. DFS 함수

   present가 target과 같아질 때 마친다.

   단, 이 때의 지나쳐 온 단어 개수와 현재 answer를 비교해서 더 작은 것을 answer에 저장한다.

 

   이 외에는 words 배열을 전체적으로 스캔하면서,

   이미 확인한 단어인지 && 현재 단어(present)와 i번째 단어(words의)가 한글자만 다른지

   를 확인한다.

      만약 해당 조건에 만족하면 visited[i]=true로 바꾸어주고 present를 words[i]로 바꿔준 다음 dfs를 재귀 호출한다.

      다른 경로가 있을 수 있으므로(차이나는 알파벳이 하나인 다른 단어가 있을 수 있으므로) visited[i]=false로 바꿔준다.

 

2. 문제에서의 "한 번에 한 개의 알파벳만 변경 가능"을 check 함수에서 확인한다.

   dfs함수에서 present 단어와 next 단어를 받아서 비교한다.

 

class Solution {
    boolean[] visited;
    int answer;
    public boolean check(String present, String next){
        int cnt = 0;
        for(int i=0; i<present.length(); i++){
            if(!present.substring(i,i+1).equals(next.substring(i,i+1))){
                cnt++;
            }
        }
        return cnt==1 ? true : false;
    }
    public void dfs(String present, String target, int count, String[] words){
        if(present.equals(target)){
            answer = (answer > count) ? count : answer;
            return;
        }
        
        for(int i=0; i<words.length; i++){
            if(!visited[i] && check(present, words[i])){
                visited[i] = true;
                dfs(words[i], target, count+1, words);
                visited[i] = false;
            }
        }
    }
    public int solution(String begin, String target, String[] words) {
        answer = words.length+1;
        visited = new boolean[words.length];        
        dfs(begin, target, 0, words);
        return answer==words.length+1 ? 0 : answer;
    }
}