[Level 3] 단어 변환

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

프로그래머스

좀 손해인 것 같지만 words 를 한 단어씩 한 단어씩의 한 문자씩 순회하면서

각 단어마다 바뀔 수 있는 단어를 그래프로 그리자

그리고 BFS 하면 될 것 같은데?

 

(코드 볼 필요 x)

import java.util.*;

class Word {
    int index;
    int count;

    Word(int index, int count) {
        this.index = index;
        this.count = count;
    }
}

class Solution {
    public int solution(String begin, String target, String[] words) {

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        ArrayList<Integer> tmp;
        Queue<Word> queue = new LinkedList<>();
        boolean[] visited = new boolean[words.length + 1];

        for (int graph_index = 0; graph_index < words.length; graph_index++) {
            tmp = new ArrayList<>();

            for (int words_index = 0; words_index < words.length; words_index++) {
                int count = 0;
                for (int word_index = 0; word_index < words[words_index].length(); word_index++) {
                    if (words[graph_index].charAt(word_index) == words[words_index].charAt(word_index))
                        count++;
                }
                if (count == words[words_index].length() - 1)
                    tmp.add(words_index);
            }

            graph.add(tmp);
        }

        tmp = new ArrayList<>();
        for (int words_index = 0; words_index < words.length; words_index++) {
            int count = 0;
            for (int word_index = 0; word_index < words[words_index].length(); word_index++) {
                if (begin.charAt(word_index) == words[words_index].charAt(word_index))
                    count++;
            }
            if (count == words[words_index].length() - 1)
                tmp.add(words_index);
        }
        graph.add(tmp);

        return bfs(graph, queue, visited, graph.size() - 1, target, words);
    }

    public int bfs(ArrayList<ArrayList<Integer>> graph, Queue<Word> queue, boolean[] visited, int start, String target, String[] words) {
        queue.add(new Word(start, 0));
        visited[start] = true;

        while (!queue.isEmpty()) {
            Word tmp = queue.remove();
            if (tmp.index != start && words[tmp.index].equals(target))
                return tmp.count;

            for (int i = 0; i < graph.get(tmp.index).size(); i++) {
                if (!visited[graph.get(tmp.index).get(i)]) {
                    queue.add(new Word(graph.get(tmp.index).get(i), tmp.count + 1));
                    visited[graph.get(tmp.index).get(i)] = true;
                }
            }

        }
        return 0;
    }
}

graph 꼭다리에는 begin 과 words[]를 비교하여 넣어 준다

 

그래프를 그리는 과정이 조금 복잡했지

bfs는 그대로인 느낌

 

O( words.length * words.length * begin.length() )