[JAVA] DFS/BFS "단어변환"

단어는 charAt메소드를 이용해서 String에서 글자를 각각 비교할 수 있다.

 

 

public class WordConversion {
    int answer;                        //최소 단계
    boolean[] used;                    //단어를 사용 중인지를 판단하는 visited와 같은 역할을 하는 배열
    public int solution(String begin, String target, String[] words) {
        answer = 51;                //단어 최대값이 50이므로
        used = new boolean[words.length];
        dfs(begin, target, 0, words);
        return answer == 51 ? 0 : answer;  //answer이 51이면 target과 같은 단어가 없는 것으로 판단.
    }
    
    public void dfs(String presentWord, String target, int count,String[] words) {
        if(presentWord.equals(target)) {
            answer = (answer > count) ? count : answer;
            return;
        }
        
        for(int i = 0; i < words.length; i++) { 
        //탐색한 글자중 하나만 차이나고 탐색되지 않은 글자이 있다면. dfs 수행
            if(!used[i] && check(presentWord, words[i])) {
                used[i] = true;
                dfs(words[i],target,count+1, words);
                used[i] = false;
            }
        }
    }
    
    public boolean check(String presentWord, String nextWord) {
    //현재의 단어와 다음 단어가 바뀔 조건에 일치하는가를 체크
        int count = 0;
        for(int i = 0; i < presentWord.length(); i++) {
            if(presentWord.charAt(i) != nextWord.charAt(i)) {
                count++;
            }
        }
        return count == 1 ? true : false;
    }
}

 

여기서도 마찬가지로, used 배열을 이용해서 단어를 사용중인지 확인하는 용도로, visited와 같은 역할로 사용한다.

 

check메소드는 charAt을 이용해서 다음 단어로 바뀔 조건에 일치하는가를 체크한다.

 

DFS을 사용하여 바뀐 단어와 target단어가 같으면 answer값을 업데이트시켜주고 사용한 단어를 체크하기 위한 used 배열과 count 매개변수를 사용하여 DFS를 재귀로 구현했다.

 

 

코드참고

tosuccess.tistory.com/29

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