[ 프로그래머스 / DFS, BFS ] 단어 변환(level 3)

Level 3 단어 변환

🤔 begin 에서 target 으로 단어 변환하기

• HashMap을 이용하여 그래프를 구성하자.
• begin 단어와 words 배열에 있는 각 단어를 그래프의 노드로 추가하고 서로 연결될 수 있는 단어들(한 글자만 다른 단어들)을 각 노드의 인접 리스트로 추가하자.

🤔 BFS 알고리즘 사용

• BFS를 사용하여 begin 단어로부터 시작이 target 단어에 도달하는 데 필요한 최소 수를 구하자.
• Queue를 사용하여 탐색할 단어들을 관리하여 각 단계에 방문한 단어와 그 단어까지 도달하는 데 필요한 단계를 저장하자.

🤔 단어 비교 함수(compareWord)

• 두 단어가 한 글자만 다른지 여부를 판단하는 함수를 만들자.
• 두 단어의  길이가 같고 서로 다른 문자의 수가 정확히 하나인 경우에만 true를 반환하자.

---

public class Main {
	public static void main(String[] args) {
    	String begin = "hit";
        String target = "cog";
        String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
        Solution10 so = new Solution10();
        System.out.println(so.solution(begin, target, words));
    }
}
class Solution {
	public int solution(String begin, String target, String[] words) {
    	Map<String, List<String>> graph = new HashMap<>();
        graph.put(begin, new ArrayList<>());
        for (int j = 0; j < words.length; j++) {
            if(compareWord(begin, words[j])) {
                graph.get(begin).add(words[j]);
            }
        }
        for (int i = 0; i < words.length; i++) {
            graph.put(words[i], new ArrayList<>());
            for (int j = 0; j < words.length; j++) {
                if(i == j) continue;
                if(compareWord(words[i], words[j])) {
                    graph.get(words[i]).add(words[j]);
                }
            }
        }
        Set<String> visited = new HashSet<>(List.of(begin));
        Queue<AbstractMap.SimpleEntry<String, Integer>> queue = new LinkedList<>(List.of(new AbstractMap.SimpleEntry<>(begin, 0)));
        while (!queue.isEmpty()) {
            AbstractMap.SimpleEntry<String, Integer> outed = queue.poll();
            System.out.println(outed);
            if (outed.getKey().equals(target)) {
                return outed.getValue();
            }
            for(String next : graph.get(outed.getKey())) {
                if(visited.contains(next)) continue;
                visited.add(next);
                queue.offer(new AbstractMap.SimpleEntry<>(next, outed.getValue() + 1));
            }
        }
        return 0;
    }
    private boolean compareWord(String s1, String s2) {
        if(s1.length() != s2.length()) return false;
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                count++;
            }
        }
        return count == 1;
    }
}