[프로그래머스/DFS] Level 3 단어 변환 (JAVA)

문제

---

풀이 (2021.01.05)

• 재귀 종료 조건은 dfs를 호출한 단어가 타겟 단어와 일치하는 경우이다.
• 호출한 단어를 만들기까지의 sequence를 visited에 기록하고, convertible한 단어들에 대해 dfs를 재귀적으로 호출한다.

코드

import java.util.Arrays;

class Solution {
    private static int answer = Integer.MAX_VALUE;

    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        Arrays.fill(visited, false);
        dfs(target, words, visited, begin, 0);
        if (answer == Integer.MAX_VALUE)
            answer = 0;
        return answer;
    }

    private void dfs(String target, String[] words, boolean[] visited, String current, int count) {
        if (current.equals(target)) {
            if (answer > count)
                answer = count;
            return;
        }

        for (int i = 0; i < words.length; i++)
            if (isConvertible(words[i], current) && !visited[i]) {
                boolean[] newVisited = Arrays.copyOf(visited, visited.length);
                newVisited[i] = true;
                dfs(target, words, newVisited, words[i], count + 1);
            }
    }

    private boolean isConvertible(String current, String word) {
        int diff = 0;
        for (int i = 0; i < current.length(); i++)
            if (current.charAt(i) != word.charAt(i))
                diff++;
        return diff == 1;
    }
}

---

풀이 (2021.05.29)

DFS로 풀면 쓸 데 없이 가장 많이 변환하는 수까지 계산해야 하니까 효율이 떨어질 것이라 생각하고, BFS로 바로 접근해서 풀었다. 근데 이전 풀이 보니까 DFS로 풀었더라ㅋㅋㅋㅋㅋㅋ큐ㅠ 눈물나는 수준의 과거의 나..

코드

import java.util.*;

class Solution {
    
    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        Queue<ConvertedWord> queue = new LinkedList<>();
        queue.offer(new ConvertedWord(begin, 0));
        while(!queue.isEmpty()) {
            ConvertedWord current = queue.poll();
            if (current.word.equals(target)) return current.count;
            
            for (int i=0 ; i<words.length ; i++) {
                if (visited[i]) continue;
                
                if (current.isConvertable(words[i])) {
                    visited[i] = true;
                    queue.offer(new ConvertedWord(words[i], current.count+1));
                }
            }            
        }
        return 0;
    }
}

class ConvertedWord {
    String word;
    int count;
    
    public ConvertedWord(String word, int count) {
        this.word = word;
        this.count = count;
    }
    
    public boolean isConvertable(String target) {
        if (word.length() != target.length()) return false;
        int count = 0;
        for (int i=0 ; i<word.length() ; i++) {
            if (word.charAt(i) != target.charAt(i))
                if (++count > 1) return false;
        }
        return true;
    }
}