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

💡 문제
단어변환 (https://school.programmers.co.kr/learn/courses/30/lessons/43163)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

---

🤓 문제 풀이

🔨 문제 설명

두 개의 단어 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단계를 거쳐 변환할 수 있습니다.

---

🔨 접근 방법

이 문제를 해결하기 위해 BFS (너비 우선 탐색)를 사용하는 이유는 BFS가 최단 경로 문제에 적합하기 때문입니다. BFS는 시작 지점에서부터 목표 지점까지의 모든 가능한 경로를 단계별로 탐색하면서, 목표 지점에 도달하는 가장 짧은 경로를 찾습니다. 이 문제에서는 각 단계를 한 글자씩 바꾸면서 진행하므로, BFS가 적합한 알고리즘입니다.

---

🔨 문제 풀이 과정

1. 큐 초기화: begin 단어와 초기 단계(0)를 큐에 넣습니다.
2. 방문 체크: 이미 방문한 단어를 추적하여 중복 변환을 방지합니다.
3. BFS 실행: 큐에서 단어를 하나씩 꺼내어 가능한 모든 단어로 변환을 시도합니다.
4. 목표 단어 확인: 변환된 단어가 목표 단어와 일치하면 변환 단계를 반환합니다.
5. 변환 실패 시: 모든 단어를 탐색해도 목표 단어에 도달하지 못하면 0을 반환합니다.

---

🔨 BFS 선택 

• 최단 경로 탐색: BFS는 최단 경로를 보장합니다. 시작 지점에서부터 모든 인접 노드를 탐색하며, 가장 먼저 목표 지점에 도달하는 경로가 최단 경로입니다.
• 단계별 탐색: 한 번에 한 글자씩 바꾸는 단계별 탐색이므로, BFS를 사용하면 각 단계를 정확히 추적할 수 있습니다.
• 효율성: BFS는 큐를 사용하여 모든 가능한 변환을 체계적으로 탐색하므로, 변환 가능한 모든 경로를 효율적으로 탐색합니다.

---

🔨 구현코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        // words 배열을 리스트로 변환합니다.
        List<String> wordList = Arrays.asList(words);

        // target 단어가 words 리스트에 없으면 0을 반환합니다.
        if (!wordList.contains(target)) {
            return 0;
        }

        // BFS를 위한 큐를 생성합니다. 큐는 현재 단어와 현재 단계를 저장합니다.
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(begin, 0));

        // 방문한 단어를 추적하기 위한 집합을 생성합니다.
        Set<String> visited = new HashSet<>();
        visited.add(begin);

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            String currentWord = currentNode.word;
            int currentStep = currentNode.step;

            // 현재 단어가 타겟 단어와 같으면 현재 단계를 반환합니다.
            if (currentWord.equals(target)) {
                return currentStep;
            }

            // words 리스트를 순회하며 한 글자만 다른 단어를 찾습니다.
            for (String word : wordList) {
                if (!visited.contains(word) && isOneLetterDifferent(currentWord, word)) {
                    visited.add(word);
                    queue.offer(new Node(word, currentStep + 1));
                }
            }
        }

        // 모든 단어를 탐색해도 타겟 단어에 도달하지 못하면 0을 반환합니다.
        return 0;
    }

    // 두 단어가 한 글자만 다른지 확인하는 함수입니다.
    private boolean isOneLetterDifferent(String word1, String word2) {
        int diffCount = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diffCount++;
            }
            if (diffCount > 1) {
                return false;
            }
        }
        return diffCount == 1;
    }

    // 큐에 저장할 노드를 표현하는 클래스입니다.
    private class Node {
        String word;
        int step;

        Node(String word, int step) {
            this.word = word;
            this.step = step;
        }
    }
}

---

📚 풀이 보완

코드 설명

• wordList 생성: words 배열을 리스트로 변환하여 더 쉽게 검색할 수 있게 합니다.
• target 존재 여부 확인: target 단어가 words 리스트에 없으면 변환이 불가능하므로 0을 반환합니다.
• BFS 큐 초기화: 큐에 begin 단어와 초기 단계(0)를 넣습니다.
• 방문 집합: visited 집합을 사용하여 이미 방문한 단어를 추적합니다.
• BFS 탐색: 큐에서 단어를 하나씩 꺼내어 가능한 모든 단어로 변환을 시도하고, 변환된 단어를 큐에 넣습니다.
• 변환 성공: 변환된 단어가 target과 일치하면 변환 단계를 반환합니다.
• 변환 실패: 모든 단어를 탐색해도 target에 도달하지 못하면 0을 반환합니다.
• isOneLetterDifferent 함수: 두 단어가 한 글자만 다른지 확인하는 함수입니다. 한 글자만 다르면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

---

📍 Plus+

공간 복잡도

• wordList 생성: words 배열을 리스트로 변환하여 저장하므로, 이 과정에서 O(n)의 공간이 소요됩니다. 여기서 n은 words 배열의 길이입니다.
• target 존재 여부 확인: 별도의 공간을 사용하지 않습니다.
• BFS 큐 초기화: 큐에는 단어와 변환 단계를 저장하므로, 큐에 저장되는 요소의 개수에 따라 공간이 변합니다. 큐에 최대 O(n)개의 요소가 들어갈 수 있습니다.
• 방문 집합: 방문한 단어를 추적하기 위해 visited 집합을 사용합니다. 이 집합의 크기는 words 배열의 길이와 동일하게 됩니다.
• BFS 탐색: 큐에는 최대 O(n)개의 요소가 들어갈 수 있습니다.
• isOneLetterDifferent 함수: 별도의 공간을 사용하지 않습니다.

따라서, 공간 복잡도는 O(n)입니다.

시간복잡도

• wordList 생성: 단어 하나마다 길이가 일정하므로, words 배열을 리스트로 변환하는 데 O(n)의 시간이 소요됩니다.
• target 존재 여부 확인: words 배열을 순회하여 target이 존재하는지 확인하는 데 최악의 경우 O(n)의 시간이 소요됩니다.
• BFS 탐색: 모든 단어를 탐색하고 변환 가능한 단어를 찾는 과정에서 최악의 경우 O(n^2)의 시간이 소요됩니다.
• isOneLetterDifferent 함수: 두 단어의 길이가 동일하므로, 한 글자만 다른지 확인하는 과정은 O(m)의 시간이 소요됩니다. 여기서 m은 단어의 길이입니다.

따라서, 시간 복잡도는 O(n^2 * m)입니다.

요약

• 공간 복잡도 : O(n)
• 시간 복잡도 : O(n^2 * m)