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

문제

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

프로그래머스

접근 방법 및 풀이

깊이 우선 탐색과 넓이 우선 탐색 두가지 방법으로 풀이

 

깊이 우선 탐색인 경우에는 이전에 변환 했던 단어를 체크 하여 동일 순환에 빠지지 않도록 처리

public class Q30_43163_dfs {
    private boolean[] visited = null;

    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        int answer = dfs(begin, target, words, 0);
        return answer > words.length ? 0 : answer;
    }

    public int dfs(String begin, String target, String[] words, int depth) {
        // 종료 조건
        // - begin과 target이 동일: 성공
        if (begin.equals(target)) {
            return depth;
        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (isConvert(begin, word) && !visited[i]) {
                visited[i] = true;
                int temp = dfs(word, target, words, depth + 1);
                visited[i] = false;
                result = Math.min(result, temp);
            }
        }

        return result;
    }

    private boolean isConvert(String word0, String word1) {
        int length = word0.length();

        int diff = 0;
        for (int i = 0; i < length; i++) {
            if (word0.charAt(i) != word1.charAt(i)) {
                diff++;
            }
        }

        return diff == 1;
    }
}

넓이 우선 탐색에서는 target으로 변환이 가능한지 우선 확인 하고 변환이 일어 날 때마다 count를 증가 시키고 target으로 변환이 완료 되면 count를 반환

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

public class Q30_43163_bfs {

    public int solution(String begin, String target, String[] words) {
        if (!Arrays.stream(words).anyMatch(item -> item.equals(target))) {
            return 0;
        }
        return bfs(begin, target, words);
    }

    public int bfs(String begin, String target, String[] words) {
        Queue<Data> queue = new LinkedList<>();

        queue.add(new Data(begin, 0));

        while (!queue.isEmpty()) {
            Data data = queue.poll();

            if (data.word.equals(target)) {
                return data.count;
            }

            for (String word : words) {
                if (isConvert(data.word, word)) {
                    queue.add(new Data(word, data.count + 1));
                }
            }
        }

        return 0;
    }

    class Data {
        public String word;
        public int count;
        public Data(String word, int count) {
            this.word = word;
            this.count = count;
        }
    }

    private boolean isConvert(String word0, String word1) {
        int length = word0.length();

        int diff = 0;
        for (int i = 0; i < length; i++) {
            if (word0.charAt(i) != word1.charAt(i)) {
                diff++;
            }
        }

        return diff == 1;
    }
}