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

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

프로그래머스

 

 

Review

이 문제도 마찬가지로 BFS와 DFS로 모두 풀어보고자 했다. 생각보다 꽤 오래 걸려서 며칠 뒤 다시 한 번 풀어봐도 좋을 것 같다.

 

 

Code

BFS ver.

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        if(!Arrays.asList(words).contains(target)) {
            return 0;
        }
        return bfs(begin, target, words);
    }
    
    private int bfs(String begin, String target, String[] words) {
        Queue<String> q = new LinkedList<>();
        boolean[] visited = new boolean[words.length];
        int count = 0;
        
        q.offer(begin);
        
        while (!q.isEmpty()) {
            int size = q.size();
            count++;
            
            for (int i = 0; i < size; i++) {
                String current = q.poll();
                
                for (int j = 0; j < words.length; j++) {
                    if (!visited[j]) {
                        int diff = 0;
                        
                        for (int k = 0; k < current.length(); k++) {
                            if (current.charAt(k) != words[j].charAt(k)) {
                                diff++;
                            }
                        }
                        
                        if (diff == 1) {
                            if (words[j].equals(target)) {
                                return count;
                            }
                            q.offer(words[j]);
                            visited[j] = true;
                        }
                    }
                }
            }
        }
        return 0;
    }
}

 

DFS ver.

class Solution {
    static boolean[] visited;
    static int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        dfs(begin, target, words, 0);
        return answer;
    }
    
    public static void dfs(String begin, String target, String[] words, int count) {
        if (begin.equals(target)) {
            answer = count;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }

            int k = 0;
            for (int j = 0; j < begin.length(); j++) {
                if (begin.charAt(j) == words[i].charAt(j)) {
                    k++;
                }
            }

            if (k == begin.length() - 1) {
                visited[i] = true;
                dfs(words[i], target, words, count + 1);
                visited[i] = false;
            }
        }
    }
}