자바(Java) 알고리즘 문제풀이 단어변환 [프로그래머스 / DFS]

출처) 프로그래머스 Facebook

 

 

 

문제 설명

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

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. 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 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

 

입출력 예시

bigin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

 

풀이 코드

DFS 를 활용한 완전탐색이기 때문에 if - else 분기를 활용해 재귀를 종료하는 부분을 꼭 설정해야한다.

words 배열의 원소 하나를 노드 하나라고 생각하고 다른 DFS 문제와 다르게 노드의 가장 깊숙한 곳까지 탐색할 필요도 없이 계속해서 갱신되는 standWord 가 원하는 target 과 일치한다면 탈출하도록 설정했다. 이후는 주석을 참고하자.

class Solution {

    static int answer = 0;
    static boolean[] checked;

    public int solution(String begin, String target, String[] words) {
        checked = new boolean[words.length];
        dfs(0, begin, target, words);

        return answer;
    }

    private static void dfs(int depth, String standWord, String target, String[] words) {
        // 노드가 가장 깊은 깊이까지 도달할 필요도 없다.
        // 갱신되는 standWord 가 target 과 일치한다면 answer 변수에 해당 depth 를 삽입한다.
        // 일치하지 않는다면 변환할 수 없는 경우므로 그대로 종료한다.
        if (standWord.equals(target)) {
            answer = depth;

        // 제공된 단어를 하나씩 비교한다. 가독성을 위해 checkDiff() 메서드를 작성
        // 비교를 했을 떄 바꿀 수 있는 단어이며 아직 체크가 안된 단어일 때 완전 탐색을 실시한다.
        } else {
            for (int i = 0; i < words.length; i++) {
                if (checkDiff(standWord, words[i]) && !checked[i]) {
                    checked[i] = true;
                    dfs(depth + 1, words[i], target, words);
                    checked[i] = false;
                }
            }
        }
    }

    private static boolean checkDiff(String standWord, String compareWord) {
        int count = 0;
        char[] a = standWord.toCharArray();
        char[] b = compareWord.toCharArray();

        // a 단어와 b 단어의 알파벳을 하나씩 비교하며 다른 알파벳이 나올 때 마다 카운팅한다.
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                count++;
            }
        }

        // 카운팅 결과가 1이 넘는다면 다른 알파벳이 1개가 넘는다는 의미이므로 변환할 수 없는 단어.
        if (count > 1) {
            return false;
        }

        // 그렇지 않을 경우 변환 가능한 단어이기 때문에 True 를 반환한다.
        return true;
    }
}

// 깊이 우선 탐색을 활용한 완전 탐색으로 진행한다.
// 방문 체크 배열을 활용해 중복 탐색을 방지하도록 하자.
// target 으로 단어를 바꿀 수 없다면 0을 반환한다.
// 최소 몇 단계의 과정을 거쳐 begin 이 target 으로 변환될 수 있는가 ?