[PGS] 단어 변환 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

class Solution {
    static int answer = Integer.MAX_VALUE;
    static boolean[] used;
    
    public int solution(String begin, String target, String[] words) {
        int n = words.length;
        used = new boolean[n];
        
        dfs(0, n, 0, begin, target, words);
        
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
    
    private void dfs(int depth, int n, int cnt, String begin, String target, String[] words) {
        if (begin.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }

        if (depth == n) {
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (used[i] || !isValid(begin, words[i])) continue;
            
            used[i] = true;
            dfs(depth+1, n, cnt+1, words[i], target, words);
            used[i] = false;
        }
    }
    
    // 알파벳이 하나만 변경되는지 확인
    private boolean isValid(String now, String next) {
        int cnt = 0;
        for (int i = 0; i < now.length(); i++) {
            if (now.charAt(i) != next.charAt(i)) {
                cnt++;
            }
        }
        
        return cnt > 1 ? false : true;
    }
}

📄 해설

접근

• DFS 를 사용하여 해결하는 문제.
• words 내의 단어들을 모두 확인하면서, 바꿀 수 있는지, 해당 단어가 target 인지를 체크하면 된다.

과정

• answer 는 최솟값이 저장되어야하니 MAX_VALUE 로 초기화 해주고, 방문배열 used 를 추가로 선언해준다.
• 바로 DFS 탐색을 시작하고, 아래와 같은 순서로 진행된다.
  • 현재 문자열인 begin 과 target 이 일치하는지 확인한다. 일치하면 최솟값을 갱신하고 종료한다.
  • 기저 조건으로 depth == n 을 설정해준다. (재귀의 종료조건이다.)
  • words 의 0번 부터 n-1 번 단어를 모두 확인한다. 이때, 이미 방문했거나 알파벳이 1개보다 많이 변경되어야 한다면 확인하지 않는다.
  • 위 조건에 해당되지 않는다면, 방문처리하고 DFS 를 수행한다.
  • DFS 를 수행하고나서는 방문처리를 해제한다.
• DFS 가 완전히 종료되고 나서, answer 의 값이 변경되었다면 그대로 반환해주고, 변경되지 않았다면 변환할 수 없는 것이므로 0을 반환해준다.