[JAVA] 단어 변환 - 프로그래머스[Lv.3]

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

프로그래머스

---

import java.util.*;
class Solution {
    static Map<String, Set<String>> maps = new HashMap<>();
    static int min = Integer.MAX_VALUE;
    static Set<String> visit = new HashSet<>();
    public int solution(String begin, String target, String[] words) {
                maps.put(begin, new HashSet<>());
        for (String word : words) {
            maps.put(word, new HashSet<>());
        }
        setMaps(-1, begin, words);
        for (int i = 0; i < words.length; i++) {
            setMaps(i, words[i], words);
        }
        visit.add(begin);
        dfs(begin, target , 0);
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    private static void setMaps(int idx, String word, String[] words) {

        for (int j = idx + 1; j < words.length; j++) {
            int cnt = 0;
            for (int i = 0; i < word.length(); i++) {
                if(word.charAt(i) == words[j].charAt(i))
                    cnt++;
            }
            if (cnt == word.length() - 1) {
                maps.get(word).add(words[j]);
                maps.get(words[j]).add(word);
            }
        }
    }

    private static void dfs(String now, String target, int cnt) {
        if(now.equals(target)){
            min = Math.min(min, cnt);
            return;
        }
        for(String s : maps.get(now)){
            if(!visit.contains(s)) {
                visit.add(s);
                dfs(s, target, cnt + 1);
                visit.remove(s);
            }
        }
    }
}

💡 DFS

풀이

• 그래프와 동일한 방식으로, 주어진 단어들과 1개를 제외하고 같은 단어들을 저장해서 DFS 탐색에 활용
  
  • 단어끼리 겹치는 char 개수 구하는 방법
    • 단어 A, B를 비교한다고 했을 때, 처음에는 단어를 split("")로 분할 해 String 단위로 한 글자씩 Set에 저장한 뒤 차집합의 크기가 1 인지 비교했음
    • 이때, Set은 자동 중복 제거되므로 "aab", "abb" 같이 제대로 처리 안되는 단어 생김, 또 위치도 중요하므로 그냥 순서대로 char 하나씩 비교하는 걸로...
• 특정 단어의 중복 사용을 방지하기 위해 중복 체크, 이때 배열 대신 set을 활용함
  
  • 사용한 단어를 set에 넣고, 재귀에서 빠져나오면 set에서 다시 제거하는 방식으로 활용