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

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

 

풀이

1. 단어가 주어진 배열에 대해서 DFS를 통해 beign이 target과 같아지는 지점을 찾는다.

2. DFS를 통해 재귀가 가능한 조건은 전에 방문하지 않았던 단어이어야 하며, 철자 하나만 다른 경우

 (visited 테이블 구성, 철자 하나만 다른지 확인하는 로직 구현)

3. 여러가지 경우가 나올 수 있으니 최소값으로 갱신하도록 한다.

 

전체 소스코드

class Solution {
    
    public int min = (int) 1e9;
    public boolean[] visited;
    
    public void process(String now, String target, String[] words, int cnt) {
        if (now.equals(target)) {
            // 여러번 가능하니 최소값으로 갱신
            min = Math.min(min, cnt);
            return;
        }
        for (int i = 0; i < words.length; i++) {
            if (visited[i]) continue;
            int check = 0;
            // 철자 하나만 다른 경우 체크
            for (int j = 0; j < now.length(); j++) {
                if (now.charAt(j) != words[i].charAt(j)) check++;
            }
            if (check == 1) {
                visited[i] = true;
                process(words[i], target, words, cnt+1);
                // 탐색끝에 아닌 경우 나올 때 방문 안한 것으로 해줘야 다음에 다시 사용 가능
                visited[i] = false;
            }
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        visited = new boolean[words.length];
        process(begin, target, words, 0);
        
        // 한번도 같은 적 없는 경우 0
        return (min == (int) 1e9) ? 0 : min;
    }
}