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

✨ BFS/DFS

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

프로그래머스

---

📍 고려해야할 점

• 한 번에 한 개의 알파벳만 변경 가능
• begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기 
• 굳이 배열의 순서대로 찾을 필요 없음

 

 

🕹️ 풀이과정

👉 이 문제 같은 경우 DFS와 BFS 모두 풀이 가능하다. 하지만 DFS로 구현할 시에는 시간복잡도가 크다.

 

🔹 DFS

1. words 배열에서 현재 단어와 한 글자만 다른 단어를 탐색한다. 👉 중복 탐색을 방지하기 위해 탐색한 단어를 방문했다는 표시를 해둔다.  
2. 탐색한 단어까지 방문한 횟수(거리)를 기록하며 탐색한 단어 기준으로 다시 탐색한다.
3. target 단어를 만나게 되면 지금까지의 방문 횟수(거리)를 비교하며 최단거리를 찾으면 된다.

 

🔹 BFS

1. DFS의 1번과 동일
2. 조건에 해당(현재 단어와 한 글자만 다름)하는 단어들을 queue에 넣는다.
3. queue에 담겨진 단어들을 기준으로 다시 탐색한다.
4. target 단어를 만나면 현재까지의 거리를 출력하면 된다. 

 

 

👩‍💻 전체 코드 - DFS

class Solution {
    
    static int min = Integer.MAX_VALUE;
    
    static void dfs(int depth, int start, String target, String begin, String[] words, boolean[] visit){
        
        if(begin.equals(target)){
            min = Math.min(min, depth);
            return;
        }
        
        if(depth==words.length) return;
        
        for(int i=0; i<words.length; i++){
            
            if(visit[i]) continue;
            String next = words[i];
            
            // 변환할 수 있는 규칙 = 한 개의 알파벳만 변환 가능 
            int cnt=0;
            for(int j=0; j<begin.length(); j++){
                if(next.charAt(j)!=begin.charAt(j)) cnt++;
            }
            if(cnt==1 && !visit[i]){
                visit[i] = true;
                dfs(depth+1, i+1, target, next, words, visit);
                visit[i] = false;
            } 
                
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        boolean[] visit = new boolean[words.length];
        
        for(int i=0; i<words.length; i++){
            visit = new boolean[words.length];
            dfs(0, 0, target, begin, words, visit);
        }
        
        if(min==Integer.MAX_VALUE) return min=0;
        else return min;
    }
}

 

 

 

 

 

👩‍💻 전체 코드 - BFS

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    static class Node {
        String next;
        int edge;

        public Node(String next, int edge) {
            this.next = next;
            this.edge = edge;
        }
    }

    public int solution(String begin, String target, String[] words) {
        int n = words.length, ans = 0;

        Queue<Node> q = new LinkedList<>();

        boolean[] visit = new boolean[n];
        q.add(new Node(begin, 0));

        while(!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.next.equals(target)) {
                ans = cur.edge;
                break;
            }

            for (int i=0; i<n; i++) {
                if (!visit[i] && isNext(cur.next, words[i])) {
                    visit[i] = true;
                    q.add(new Node(words[i], cur.edge + 1));
                }
            }
        }
        return ans;
    }

    static boolean isNext(String cur, String n) {
        int cnt = 0;
        for (int i=0; i<n.length(); i++) {
            if (cur.charAt(i) != n.charAt(i)) {
                if (++ cnt > 1) return false;
            }
        }
        return true;
    }    
}