[프로그래머스] 단어 변환 Lv3 JAVA [DFS][엄탱]

문제 링크

프로그래머스

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot", "dot", "dog", "lot", "log", "cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해 주세요.

해설

나는 이상하게 문자열만 나오면 겁부터 먹는다...

처음 접근을 DFS로 탐색하는데 기준이 되는 단어와 탐색한 단어가 한 개의 알파벳만 다른지 다 체크하면 시간초과가 발생하지 않을까? 다른 방법이 있을 것 같은데.. 하면서 해보지도 않고 안된다 판단하였다.

그래서 이번 문제는 질문에서 도움을 받았는데 내가 생각한 방법대로 해도 통과할 수 있다는 것을 알게 되었다...

 

해당 문제는 begin을 시작으로 DFS 탐색을 하면서 조건에 맞는 단어를 찾아가면서 최종적으로 target이 몇 단계가 되는지 최솟값을 찾으면 된다.

 

접근 방법은 이렇다.

1. 탐색을 체크하는 배열을 만든다. 이번에 탐색 배열은 중요한 게 한번 탐색했던 단어는 DFS로 탐색이 끝나면 다시 탐색이 필요한(false) 단어로 변경해 주는 게 핵심이다.

2. 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;
    }

    private void dfs(int idx, int count, String begin, String target, String[] words, boolean[] visited) {
        if (idx >= words.length) {
            return;
        }

        if (begin.equals(target)) {
            answer = Math.min(answer, count);
            return;
        }


        for (int i = 0; i < words.length; i++) {
            if (visited[i] || answer <= count || !ckWord(begin, words[i])) {
                continue;
            }

            visited[i] = true;
            dfs(i, count + 1, words[i], target, words, visited);
            visited[i] = false;
        }
    }

    private boolean ckWord(String begin, String target) {
        int differentCount = 0;
        for (int i = 0; i < begin.length(); i++) {
            if (begin.charAt(i) != target.charAt(i)) {
                differentCount++;

                if (differentCount >= 2) {
                    return false;
                }
            }
        }

        return true;
    }
}