[lv.3] 단어 변환

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

• 문제
  

• 나의 풀이
  1) words에 target의 유무를 따져 없으면 0으로 리턴
  2) words의 각 인덱스의 char를 담은 HashSet의 ArrayList를 만든다.
  (["hot", "dot", "dog", "lot", "log", "cog"] 라면 list는 [[c, d, h, l], [o], [t, g]])
  3) DFS나 BFS로 각 인덱스에 위의 list에 있는 알파벳으로 대체하여 만든 newStr를 만든다.
  4) 해당 newStr가 words에 있고 이미 만들었던 문자열이 아니면 큐에 넣거나 DFS로 다시 시작.
  (만일, 만들어진 newStr를 저장하지 않을 경우 테스트3에서 시간초과가 난다.)
  5) target과 newStr이 같아질때까지 반복 (만일 words에 target이 있다면 무조건 성공한다.)

• 다른 사람의 풀이 (DFS)
  1) 한 글자 빼고 나머지가 같은 단어를 words에서 찾는다.
  2) 찾은 단어를 visited = true 로 설정해 준다.
  3) cnt를 증가시키며 dfs 함수를 재귀 호출한다.
  4) 모든 경우의 수를 보기 위해 visited = false로 재설정한다.
  5) begin과 target이 같은 경우, cnt를 answer에 대입하고 종료한다.

  출처 : https://velog.io/@hammii/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98-java

• 소감
  중복 처리에서 자꾸 애를 먹었다.
  lv.3를 자력으로 50분으로 푼다고 하면....가망없는데...

• 나의 코드 (DFS)

import java.util.*;

class Solution {
    static boolean[] check;
    static int result = Integer.MAX_VALUE;
    static HashSet<String> set = new HashSet<>();
    static HashSet<String> memory = new HashSet<>();
    static ArrayList<HashSet<Character>> list;
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        check = new boolean[target.length()];
        for(int i=0; i<words.length; i++){
            set.add(words[i]);
        }
        if(!set.contains(target)) return 0;
        list = new ArrayList<>();
        for(int i=0; i<begin.length(); i++){
            HashSet<Character> listSet = new HashSet<>();
            for(int j=0; j<words.length; j++){
                listSet.add(words[j].charAt(i));
            }
            list.add(listSet);
        }
        dfs(begin, target, 1);
        answer = result;
        return answer;
    }
    public void dfs(String now, String target, int cnt){
        if(cnt==target.length()+1) check = new boolean[target.length()];
        if(now.equals(target)){
            result = Math.min(result, cnt-1);
            return;
        }
        for(int i=0; i<target.length(); i++){
            if(!check[i]){
                check[i] = true;
                Iterator<Character> iter = list.get(i).iterator();
                while(iter.hasNext()){
                    char cur = iter.next();
                    String newStr = now.substring(0, i)+cur+now.substring(i+1);
                    if(set.contains(newStr) && !memory.contains(newStr)){
                        memory.add(newStr);
                        dfs(newStr, target, cnt+1);
                    }
                }
                check[i] = false;
            }
        }
    }
}

• 나의 코드 (BFS)

import java.util.*;

class NowString{
    String str;
    int cnt;
    public NowString(String str, int cnt){
        this.str = str;
        this.cnt = cnt;
    }
}

class Solution {
    static HashSet<String> set = new HashSet<>();
    static HashSet<String> memory = new HashSet<>();
    static ArrayList<HashSet<Character>> list;
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        for(int i=0; i<words.length; i++){
            set.add(words[i]);
        }
        if(!set.contains(target)) return 0;
        list = new ArrayList<>();
        for(int i=0; i<begin.length(); i++){
            HashSet<Character> listSet = new HashSet<>();
            for(int j=0; j<words.length; j++){
                listSet.add(words[j].charAt(i));
            }
            list.add(listSet);
        }
        answer = bfs(begin, target);
        return answer;
    }
    public int bfs(String begin, String target){
        Queue<NowString> queue = new LinkedList<>();
        queue.add(new NowString(begin, 0));
        while(!queue.isEmpty()){
            NowString now = queue.poll();
            if(now.str.equals(target)) return now.cnt;
            for(int i=0; i<target.length(); i++){
                Iterator<Character> iter = list.get(i).iterator();
                while(iter.hasNext()){
                    char cur = iter.next();
                    String newStr = now.str.substring(0, i)+cur+now.str.substring(i+1);
                    if(set.contains(newStr) && !memory.contains(newStr)){
                        memory.add(newStr);
                        queue.add(new NowString(newStr, now.cnt+1));
                    }
                }
            }
        }
        return 0;
    }
}

• 다른 사람의 풀이 (DFS)

class Solution {
    static boolean[] visited;
    static int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        dfs(begin, target, words, 0);
        return answer;
    }
    
    public static void dfs(String begin, String target, String[] words, int cnt) {
        if (begin.equals(target)) {
            answer = cnt;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }

            int k = 0;    // 같은 스펠링 몇개인지 세기
            for (int j = 0; j < begin.length(); j++) {
                if (begin.charAt(j) == words[i].charAt(j)) {
                    k++;
                }
            }

            if (k == begin.length() - 1) {  // 한글자 빼고 모두 같은 경우
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visited[i] = false;
            }
        }
    }
}