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

코드 힌트

BFS 접근 방법:

1. 큐 사용:
   • 큐를 사용하여 탐색을 수행합니다. 큐에는 현재 단어와 변환 단계 수를 함께 저장합니다.
   • 현재 단어와 단계 수를 큐에서 꺼내어 처리하고, 다음 단계로 넘어갈 때는 새 단어와 단계 수를 큐에 추가합니다.
     

     Queue<Node> queue = new LinkedList<>();
     queue.add(new Node(currentWord, currentStep));
     while (!queue.isEmpty()) {
         Node node = queue.poll();
         // 처리 코드
     }

     
     
     
2. 방문 기록:
   • 방문 기록 배열을 사용하여 이미 방문한 단어를 체크합니다. 이는 중복된 탐색을 방지하고, 효율적으로 탐색할 수 있도록 도와줍니다.
   • 방문한 단어는 큐에 다시 추가되지 않도록 합니다.
     

     boolean[] visited = new boolean[words.length];
     if (!visited[i]) {
         visited[i] = true;
         queue.add(new Node(nextWord, currentStep + 1));
     }

     
     
     
     
3. 변환 가능성 검사:
   • 두 단어가 한 글자만 다른지 검사하여 변환이 가능한지 확인합니다.
   • 변환 가능하면 큐에 새 단어와 단계 수를 추가합니다.

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;

 

 

DFS 접근 방법:

1. 재귀적 탐색:
   • 깊이 우선 탐색을 위해 재귀적으로 단어를 탐색합니다.
   • 현재 단어가 목표 단어와 같으면 변환 단계를 기록합니다. 이 단계는 DFS의 깊이에 따라 달라질 수 있습니다.
2. 방문 기록:
   • 방문 기록 배열을 사용하여 현재 탐색 중인 단어를 기록하고, 탐색 후에는 상태를 원상복구합니다. 이로 인해 동일 단어를 여러 번 방문하지 않도록 합니다.
3. 변환 가능성 검사:
   • 두 단어가 한 글자만 다른지 검사하여 변환이 가능한지 확인합니다.
   • 가능한 변환을 수행하고, 재귀적으로 탐색을 계속합니다.

BFS가 DFS보다 효율적인 이유

1. 최단 경로 보장:
   • BFS는 모든 가능한 경로를 동일한 수준에서 탐색하기 때문에 최단 변환 단계를 보장합니다. BFS의 첫 번째 성공적인 변환이 목표 단어에 도달한 최단 경로입니다.
   • DFS는 깊이 우선으로 탐색하므로, 최단 경로를 보장하지 않습니다. 복잡한 경로를 깊게 탐색할 수 있으며, 최단 경로를 찾지 못할 수도 있습니다.
2. 탐색 범위:
   • BFS는 각 단계에서 모든 가능한 변환을 폭넓게 탐색합니다. 이는 모든 경로를 균형 있게 탐색하여 최단 경로를 찾는 데 유리합니다.
   • DFS는 깊이 우선 탐색으로 인해 긴 경로를 탐색하고 되돌아오는 과정에서 비효율적일 수 있습니다. 메모리와 시간 자원을 많이 소모할 수 있습니다.
3. 시간 복잡도:
   • BFS는 계층적으로 탐색을 수행하므로, 최단 경로를 찾는 데 일반적으로 효율적입니다. 상태가 겹치지 않도록 탐색하며, 최단 경로를 찾는 데 최적화됩니다.
   • DFS는 깊이까지 탐색하므로 많은 경우 비효율적입니다. 깊은 경로를 계속 탐색하면서 최단 경로를 찾기 어려울 수 있습니다.

 

 

---

정답은 더보기 클릭

BFS

import java.util.*;

class Solution {
    
    // BFS를 위한 상태를 저장하는 클래스
    class Node {
        String word;  // 현재 단어
        int count;    // 변환 단계
        
        public Node(String word, int count) {
            this.word = word;
            this.count = count;
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        // BFS 큐 초기화
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(begin, 0));  // 시작 단어와 초기 단계 0을 큐에 추가
        
        // 방문 기록 배열
        boolean[] visited = new boolean[words.length];  // 각 단어의 방문 여부를 기록
        int result = 0;  // 최단 변환 단계 저장
        
        while(!queue.isEmpty()) {
            Node currentNode = queue.poll();  // 큐에서 현재 노드 꺼내기
            String currentWord = currentNode.word;  // 현재 단어
            int currentCount = currentNode.count;  // 현재 변환 단계
            
            // 타겟 단어를 찾으면 변환 단계 반환
            if (currentWord.equals(target)) {
                result = currentCount;
                break;  // 목표 단어를 찾으면 반복 종료
            } 
            
            // 모든 단어에 대해 변환 가능성을 검사
            for (int i = 0; i < words.length; i++) {
                if (!visited[i] && canTransform(currentWord, words[i])) {
                    visited[i] = true;  // 현재 단어를 방문했다고 기록
                    queue.add(new Node(words[i], currentCount + 1));  // 다음 단계로 큐에 추가
                }
            }
        }
        
        return result;  // 최단 변환 단계 반환
    }
    
    // 두 단어가 한 글자만 다른지 확인하는 함수
    static boolean canTransform(String word1, String word2) {
        int count = 0;  // 다른 문자 개수 세기
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                if (++count > 1) return false;  // 두 단어가 한 글자만 다를 때만 true
            }
        }
        
        return true;  // 한 글자만 다를 때 true 반환
    }
}

 

DFS

import java.util.*;

class Solution {

    static int n;  // 단어의 길이
    static int answer;  // 최단 변환 단계 저장
    
    public int solution(String begin, String target, String[] words) {
        answer = Integer.MAX_VALUE;  // 최단 변환 단계를 무한대로 초기화

        // words 배열에 target이 존재하지 않는다면 변환 불가능하므로 0 반환
        if (!Arrays.asList(words).contains(target)) {
            return 0;
        }
        
        n = begin.length();  // 단어 길이 설정
        boolean[] visited = new boolean[words.length];  // 각 단어의 방문 여부 기록
        dfs(begin, target, words, visited, 0);  // DFS 탐색 시작
        return answer == Integer.MAX_VALUE ? 0 : answer;  // 최단 변환 단계 반환, 변환 불가능 시 0 반환
    }

    // 깊이 우선 탐색 (DFS) 함수
    static void dfs(String currentWord, String target, String[] words, boolean[] visited, int result) {
        if (currentWord.equals(target)) {  // 목표 단어에 도달한 경우
            answer = Math.min(result, answer);  // 현재 단계와 기존 최단 단계 비교하여 최소값 갱신
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (!visited[i] && canTransform(currentWord, words[i])) {  // 방문하지 않았고 변환 가능하면
                visited[i] = true;  // 현재 단어를 방문했다고 기록
                dfs(words[i], target, words, visited, result + 1);  // 재귀적으로 탐색
                visited[i] = false;  // 상태를 원상복구 (백트래킹)
            }
        }
    }
    
    // 두 단어가 한 글자만 다른지 확인하는 함수
    static boolean canTransform(String word1, String word2) {
        int count = 0;  // 다른 문자 개수 세기
        for (int i = 0; i < n; i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                count++;  // 다른 문자가 있으면 count 증가
            }
        }
        return count == 1;  // 다른 문자가 딱 하나만 있을 때 true 반환
    }
}