[Programmers] 단어변환 문제 풀이

boolean[] visited;
int minStep;

int countWord(String begin, String target, String[] words) {
    visited = new boolean[words.length + 1];
    minStep = Integer.MAX_VALUE;

    for (int i = 1; i <= words.length; i++) {
        dfs(begin, target, words, 0, i);
    }

    return minStep == Integer.MAX_VALUE ? 0 : minStep;
}

private void dfs(String nowWord, String target, String[] words, int step, int wordIndex) {
    if (target.equals(nowWord)) {
        minStep = Math.min(step, minStep);
    } else if (wordIndex > words.length) {
        return;
    }

    visited[wordIndex - 1] = true;
    for (int i = 1; i <= words.length; i++) {
        if (visited[i]) continue;
        if (!isCanChange(nowWord, words[i - 1])) continue;

        dfs(words[i - 1], target, words, step + 1, i + 1);
    }
    visited[wordIndex - 1] = false;
}

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

import java.util.LinkedList;
import java.util.List;

class Solution {

    public int solution(String begin, String target, String[] words) {
        WordGraph wordConverter = new WordGraph(words);
        return wordConverter.step(begin, target);
    }
    
    private class WordGraph {
        int step;
        Word[] words;

        public WordGraph(String[] words) {
            this.words = new Word[words.length + 1];
            for (int i = 1; i <= words.length; i++) {
                this.words[i] = new Word(words[i - 1]);
                for (int j = 1; j < i; j++) {
                    if (!isCanChange(this.words[i].data, this.words[j].data)) continue;

                    addEdge(i, j);
                }
            }
        }

        private void addEdge(int i, int j) {
            Word word = words[i];
            Word word1 = words[j];

            if (!word.adjacents.contains(word1)) {
                word.adjacents.add(word1);
            }
            if (!word1.adjacents.contains(word)) {
                word1.adjacents.add(word);
            }
        }

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

        public int step(String begin, String target) {
            step = Integer.MAX_VALUE;

            Word beginWord = new Word(begin);
            words[0] = beginWord;

            for (int i = 1; i < words.length; i++) {
                if (!isCanChange(words[0].data, words[i].data)) continue;
                addEdge(0, i);
            }

            dfs(beginWord, target, 0);

            return step == Integer.MAX_VALUE ? 0 : step;
        }

        private void dfs(Word word, String target, int step) {
            if (word.data.equals(target)) {
                this.step = Math.min(this.step, step);
                return;
            }
            if (word.marked) return;

            word.marked = true;
            for (Word adjacent : word.adjacents) {
                if (adjacent.marked) continue;
                dfs(adjacent, target, step + 1);
            }
            word.marked = false;
        }

        class Word {
            String data;
            boolean marked;

            List<Word> adjacents;
            public Word(String data) {
                this.data = data;
                adjacents = new LinkedList<>();
            }

            public boolean canChange(String word) {
                int diff = 0;
                for (int i = 0; i < data.length(); i++) {
                    if (data.charAt(i) != word.charAt(i)) diff++;
                }

                return diff == 1;
            }
        }
    }
}