[프로그래머스] lv3. 단어변환 [#BFS/DFS]

 

 

 

---

1. 문제 출처

---

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

프로그래머스

 

1) 문제 이해

단어 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾아라

 

제약사항

1) 한 번에 한 개의 알파벳만 변환 가능

2) words에 있는 단어로만 변환 가능

 

 

예시

begin : hit

target : cog

words : [ "hot","dot","dog","lot","log","cog" ]

정답 : 4회

 

처음부터 c를 h로 바꿀 수 없다. words에 hog라는 단어가 없기 때문이다.

i를 o로 바꿔 (1) hot으로 바꾼다.

 

근데 가만 보다보니 결국 답은 words안에 있고, begin 단어도 결국 words에 있는 단어로만 바뀐다.

 

처음에 begin단어와 1개만 다른 words를 시작으로 1개만 다른 words의 조합을 찾아 떠나면 어떨까?

 

 

---

2. 설계 및 답변

---

 

1) BFS 설계

현재단어 = (hit, 0) 큐 = [(hot,1)]

현재단어 = (hot, 1) 큐 = [(dot, 2), (lot, 2)]

현재단어 = (dot, 2) 큐 = [ (lot, 2), (dog, 3)] //hot, lot은 이미 들어갔으니 제외

현재단어 = (lot, 2) 큐 = [ (dog, 3), (log, 4)] // hot, dot 은 이미 들어갔으니 제외

현재단어 = (dog, 3)  큐 = [(log, 4), (cog, 4)] // dot, log 은 이미 들어갔으니 제외

현재단어 = (log, 4)  큐 = [(cog, 4)] // dog, lot, cog는 이미 들어갔으니 제외

현재단어 = (cog, 4)

 

정답은 4

 

짧은 변환 과정을 찾는 것이니 중복을 넣어주지 않아도 된다고 생각했다.

가장 긴 변환과정을 찾았다면 중복을 넣어줬을 것이다.

 

 

2) 코드

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    
    public static class Order implements Comparable<Order>{
        String word;
        int order;
        
        public Order(String word, int order){
            this.word = word;
            this.order = order;
        }
        
        @Override
        public int compareTo(Order o){
            return this.order>o.order?1:-1;
        }
    }
    
    static int result = 987654321;
    
    public int solution(String begin, String target, String[] words) {
        
        if(Arrays.asList(words).contains(target)){
            BFS(begin, target, words);   
        }else{
            result=0;
        }
        
        if(result==987654321) result=0;
        
        return result;
    }
    
    public static void BFS(String begin, String target, String[] words){
        Queue<Order> q = new LinkedList<>();
        boolean[] visited = new boolean[words.length];
        
        //첫 값 넣어주기
        q.offer(new Order(begin,0));
        visited[0] = true;
        
        while(!q.isEmpty()){
            Order cur = q.poll();
            
            if(cur.word.equals(target)){
                result = cur.order;
                return;
            }
            
            //한글자 다른거 찾아서 큐에 넣어주기
            for(int idx=0; idx<words.length; idx++){
                
                int diff = 0; //다른 글자가 1개여야 함
                
                //같은 글자나 이미 들어갔던 글자 비교 금지
                if(words[idx].equals(cur.word)) {
                    continue;
                }
                
                for(int i=0;i<words[idx].length();i++){
                    
                    if(words[idx].charAt(i)!=cur.word.charAt(i)){
                        diff++;
                    }
                }
                
                if(diff==1){
                      q.offer(new Order(words[idx],cur.order+1));
                }
            }
            
        }
        
        
    }
}

 

3) 반례

입력값 〉 "hit", "cog", ["cog", "log", "lot", "dog", "dot", "hot"]
기댓값 〉 4

 

 

4) 배운것

Arrays.asList(words).contains(target)

asList는 배열을 ArrayList로 바꿔주는 녀석이다.

ArrayList의 contains를 사용해 words에 tartget 단어가 있는지 체크하고 BFS를 돌았다.

이 과정 없이 바로 BFS를 돌았더니 무한 루프가 났다.

 

 

---

3. DFS 설계 및 답변

---

1) DFS 설계

1회 -> 5회 변환 과정

hit

hit > hot

hit > hot  > dot

hit > hot > dot > dog

hit > hot > dot > dog > log

hit > hot > dot > dog > log  > cog

 

2회 : cog를 선택하지 않은 경우 -> 답이 될 수 없음 제외

 

3회 : log를 선택하지 않은 경우 -> 4회 변환 과정

hit

hit > hot

hit > hot  > dot

hit > hot > dot > dog

hit > hot > dot > dog > cog

 

.

.

.

 

이런식으로 DFS로 들어간 후 target 단어가 완성되면 1회를 추가해주는 것이다.

또한 target 단어가 words에 없을 경우(변환할 수 없는 경우) return은 0이다.

 

모든 경우의 깊이를 조사해봐야 알 수 있으므로 시간 내 모든 테스트를 통과하기란 무리라고 판단했고, BFS로만 코드를 짰다.