Java - [프로그래머스]43163-단어 변환

출처

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

문제

begin 단어를 아래와 같은 규칙을 이용하여 target으로 바꾸는 가장 짧은 과정을 찾는 문제입니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있다
2. words안에 있는 단어로만 변환할 수 있다.

변환 할 수 없는 경우 0을, 가능한 경우 가장 짧은 과정의 수를 return합니다.

풀이

DFS를 통해 해결하려고 합니다. DFS를 통해 기준이 되는 단어와 현재 탐색한 단어가 하나만 다른지 전부 체크하도록 하였습니다.

dfs함수를 선언하여 인덱스 0부터 탐색을 시작하도록 합니다. 풀이 과정은 다음과 같습니다.

1. visted를 통해 사용한 배열인지 체크합니다.
2. checkWord를 사용하여 한 단어만 다른지 체크합니다.
3. 효율성을 위해 만약 기존의 answer이 존재하고, 현재 센 count가 기존의 answer보다 작다면 건너뛰도록 합니다.
4. 위 3개 조건중 하나도 충족하지 않는다면, 현재 탐색한 문자열을 words[i]로 바꾼 뒤 그 지점부터 다시 dfs를 진행합니다.
5. 종료조건이 충족되면 count와 answer중 작은것을 answer에 저장합니다.

재귀에서 가장 중요한 종료 조건은 begin == target일 경우로 잡았습니다. 또한 중요한 점은 탐색이 시작되기 전 true로 해놓았던 곳은 dfs가 종료되면 다시 false로 바꾸어 주어야 합니다. 그래야 다른 인덱스에 대해서도 dfs가 정상적으로 동작할 수 있습니다.

코드

class Solution {
    int answer = Integer.MAX_VALUE;
    
    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        dfs(0, 0, begin, target, words, visited);
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
    
    public void dfs(int idx, int count, String begin, String target, 
             String[] words, boolean[] visited) {
        if(begin.equals(target)) {
            answer = Math.min(answer, count);
        }
        for(int i = 0; i < words.length; i++) {
            if(visited[i] || !checkWord(begin, words[i]) || answer <= count) {
                continue;
            }
            visited[i] = true;
            dfs(i, count+1, words[i], target, words, visited);
            visited[i] = false;
        }   
    }
    
    public boolean checkWord(String a, String b) {
        int diff = 0;
        for(int i = 0; i < a.length(); i++) {
            if(a.charAt(i) != b.charAt(i)) diff++;
        }
        if (diff > 1) return false;
        return true;
    }
    
    
}