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

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 begin 단어에서 시작
2. words 배열에서 알파벳 차이가 1개 나는 단어를 찾아 dfs로 반복하며 count + 1
3. 함수에 들어온 단어가 target과 동일하면 이 때의 count를 답과 비교해 교체

 문제에서 주어진 배열의 길이가 그렇게 길지 않기 때문에, dfs를 사용하여 모든 경우의 수를 탐색하기에 충분하여 dfs 기반으로 함수를 작성했다.

 문제의 전체적인 풀이 과정으로는 우선 words 배열과 target을 비교해 답을 찾을 수 있는 지 없는 지를 우선 확인한 다음, dfs 탐색 여부 배열을 초기화하고 begin 단어를 시작으로 dfs 탐색을 시작한다. 이후 dfs 배열에서는 words 배열 중 탐색안한 단어와 알파벳 차이가 1개인 단어를 찾아 해당 단어를 시작으로 다시 dfs 탐색을 시작하고, 최종적으로 target 단어와 동일한 경우 여태까지 쌓인 count를 답과 비교해 최소값을 답으로 최신화하도록 작성했다.

class Solution {
    boolean[] visited;//dfs 탐색 여부 배열
    int answer = 99;

    public int solution(String begin, String target, String[] words) {
        if (!checkTarget(target, words)) //words에 target이 없으면 0 반환
            return 0;

        visited = new boolean[words.length]; //dfs 탐색 여부 배열 초기화

        dfs(begin, target, 0, words); //begin 단어를 시작으로 dfs 탐색

        if (answer == 99) //답이 없으면 0 반환
            return 0;

        return answer;
    }

    private boolean checkTarget(String target, String[] words) {//target과 동일한 단어 존재 여부 확인
        for (String word : words)
            if (word.equals(target))
                return true;

        return false;
    }

    private void dfs(String word, String target, int count, String[] words) {
        if (word.equals(target)){
            answer = Math.min(answer, count);
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (!visited[i]) {
                if (countDiff(word, words[i]) == 1) {
                    visited[i] = true;
                    dfs(words[i], target, count + 1, words);
                    visited[i] = false;
                }
            }
        }
    }

    private int countDiff(String a, String b) {//두 단어간 알파벳 차이 반환
        int diff = 0;

        for (int i = 0; i < a.length(); i++)
            if (a.charAt(i) != b.charAt(i))
                ++diff;

        return diff;
    }
}

결과