[JAVA] 단어 변환(코딩테스트 고득점 Kit [깊이/너비 우선탐색(DFS/BFS)]) - LEVEL3

📂문제 설명

 

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin                               target                               words                              return

hit	cog	[hot, dot, dog, lot, log, cog]	4
hit	cog	[hot, dot, dog, lot, log]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

---

📂아이디어 및 알고리즘(문제풀이)

• 문제의 핵심은 한 단어에서 한 단어로 이동할 때마다 ArrayList에 넣어주고 그 list값들을 순회하면서 DFS로 target값에 도달하게 해주는 것이다. 그러면 몇 번만에 도달했는지를 알 수 있게 된다.
• target 단어가 있는지 확인하여 있으면 마지막 Index값과 변경하여 맨 뒤로 보내준다.
  • check를 이용하여 false면 target값이 없는 걸 의미한다. [ return 0; 으로 종료 해준다. ]
• 여기서 중요한건 단어에서 한 단어로 바뀔때는 반드시 하나의 문자만 달라야 변경할 수 있다.
• 그래서 DFS에서 count를 통해 1개의 글자만 변경되는 경우 index값을 list에 추가하여 다음 DFS로 보내도록 하였다.
• 즉, list에 저장된 words[]의 index값으로 순회하여 DFS로 날려주게 되면 한 글자 한 글자씩 이동하여 target값을 찾게된다.
• target값에서 depth를 비교해 최솟값을 찾아준다.

📂소스 코드

import java.util.ArrayList;
class Solution {
    
    static int min;
    public int solution(String begin, String target, String[] words) {
        boolean check = false;
        min = words.length;
        
        
        // 먼저 배열에 target단어가 있는지를 확인한다. 
        // 그리고 target단어가 있으면 맨 마지막 index에 가져다 놓는다. 
        int index=0;
        for(String s : words){
            if(target.equals(s)){
                check=true;
                String temp = words[index];
                words[index] = words[words.length-1];
                words[words.length-1] = temp;                
            }
            index++;
        }
        if(check == false) return 0;
        
        DFS(begin, target, words, -1, 0);
        
        return min;
    }
    
    public static void DFS(String begin, String target, String[] words, int index, int depth){
        if(begin.equals(target) == true){
            if(depth < min){
                min=depth;
            }
            return;
        }
        if(index < words.length){
            
            //begin에서 다음단어로 갈 수 있는 단어에 대해 선택지를 세어 list에 넣어준다.
            //그러면 매번 돌때마다 갈 수 있는 선택지를 저장하게 되고 갈 수 있는 곳으로만 DFS를 날려준다. 
            
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int k=index+1;k<words.length;k++){
                int c=0;
                for(int i=0;i<begin.length();i++){
                    if(begin.charAt(i) != words[k].charAt(i)){
                        c++;
                    }
                }
                if(c == 1) list.add(k);
            }
            for(int x : list){
                DFS(words[x],target,words,x,depth+1);
            }
        }
    }
    
}