[프로그래머스] 단어 변환(Level 3, JAVA, 왜 BFS를 사용해야 하나?, BFS/DFS, 깊이 탐색, 너비 탐색)

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

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

 

 

 

## 문제접근

---

시작 단어에서 출발하여서 타겟 단어로 만들어야 한다. 그 과정은 최소가 되어야 한다. 최소가 되기 위해선, 최적의 단어 순서를 찾는 것뿐만 아니라, 중복해서 단어를 방문해서는 절대 안된다. 

 

 

 

단어의 중복 방문은 무한 루프에 빠지게 할 수 있다. 최적의 단어 순서를 찾기 위해서 완전 탐색을 이용하고 중복된 단어를 방문하지 않기 않도록 한다.

 

 

 

완전 탐색의 기법은 DFS와 BFS가 있다. DFS를 써서 문제를 풀면 시간 복잡도는 어떻게 될까? DFS는 모든 단어 조합을 탐색하지만, 불필요한 깊이까지의 탐색이 이루어지고 BFS보다 더 많은 단어 순서를 확인하게 된다.

 

 

 

A에서 이동할 수 있는 단어가 B, C, D라고 생각하면 DFS라면 A->B, A->C, A->D 순서로 백트래킹하게 된다. 또한 만약에, B에서 C나 D로 이동할 수 있게 된다면 DFS는 또 탐색을 시작할 것이다.

 

 

 

반면에 BFS는 A에서 B, C, D를 같은 깊이(시간)에 탐색하게 된다. 따라서 B에서 C나 D로 이동할 일은 전혀 없다. 왜냐면, 이미 깊이가 1에서 C와 D를 이동할 수 있는데, 깊이가 2에서 C와 D를 이동하는건 최소의 단어 변환의 목적과 맞지 않기 때문이다.

 

 

 

N을 단어 조합의 개수라고 할 때, BFS의 시간 복잡도는 O(N)이지만, DFS의 시간 복잡도는 최악의 경우 O(N^10)까지 발생할 수 있다. 테스트 케이스가 약해서 DFS와 BFS가 모두 가능했지만, BFS를 무조건 활용해야 한다.

 

 

 

BFS를 이용해서, String과 Integer가 큐의 아이템으로 들어가게 하면 된다. String은 단어 변환의 현재를 나타내고, Integer은 단어 변환의 깊이를 의미한다.

 

 

 

 

## 해설코드

---

 

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    class Item{
        String str;
        int move;
        Item(String str, int move){
            this.str = str;
            this.move = move;
        }
    }
    boolean isCanConvert(String str1, String str2){
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        
        for(int i = 0; i < str1.length(); i++){
            cnt1[str1.charAt(i) - 'a']++;
            cnt2[str2.charAt(i) - 'a']++;
        }
        
        int diff = 0;
        for(int i = 0; i < 26; i++){
            diff += (Math.abs(cnt1[i] - cnt2[i]));
        }
        
        return diff == 2 ? true : false;
    }
    
    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        Queue<Item> q = new LinkedList<>();    
        q.add(new Item(begin, 0));
        
        while(!q.isEmpty()){
            Item item = q.poll();
            if(item.str.equals(target))
                return item.move;
            
            for(int i = 0; i < words.length; i++){
                if(isCanConvert(item.str, words[i]) && !visited[i]){
                    visited[i] = true;
                    q.add(new Item(words[i], item.move + 1));
                }
            }
        }
        
        return 0;
    }
}