[200425] 깊이/너비우선탐색(DFS, BFS) - 단어변환(level3)

1. 문제이해

- 한 번에 한 개의 알파벳을 바꿔 words에 있는 단어로 변환하면서 target과 같은 단어를 만들기

- 조건에 만족하는 결과가 다음으로 연결되는 "노드"로 생각하면 된다!!

 

2. 전략

**BFS를 이용 : 최소 단계를 구하는 것이므로 depth가 작아야 된다!!

① Vocab 클래스 : 현재 단계를 함께 저장하기 위해 word와 level을 함께 넣을 클래스가 필요

② BFS 요소 : 큐, check 배열

③ BFS

- 큐가 빈 경우 : 방법을 찾지 못한 경우이므로 answer = 0으로 끝남

- target을 찾은 경우 : 해당 Vocab의 level을 answer로

- 이미 check배열에 있거나 현재 시작노드와 같은 단어인 경우 : continue

- 변환 가능한 단어 찾기 : substring(0, j), substring(j+1, size)들끼리 비교 --> q에 넣고, check해주기

 

3. 참고사항

- String : "substring"은 subString이 아님을 유의

 

4. 코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        int size = begin.length();
        class Vocab{
            public String word;
            public int level;
            Vocab(String w, int l){
                this.word = w;
                this.level = l;
            }
        }
        //BFS
        Queue<Vocab> q = new LinkedList<>();
        boolean[] check = new boolean[words.length];
        q.add(new Vocab(begin, 0));
        Vocab current = null;
        if(begin.equals(target)){
            answer = 0;
        }
        while(!q.isEmpty()){
            current = q.poll();
            if(current.word.equals(target)){ //target을 찾은 경우
                answer = current.level;
                break;
            }
            for(int i = 0; i < words.length; i++){
                if(check[i] || current.word.equals(words[i])){ //이미 변환했던 경우, 같은 단어인 경우
                    continue;
                }
                for(int j = 0; j < size; j++){ //변환 가능한 단어 찾기
                    if((words[i].substring(0, j)).equals(current.word.substring(0, j)) 
                       && (words[i]. substring(j+1, size)).equals(current.word.substring(j+1, size))){
                        check[i] = true;
                        q.add(new Vocab(words[i], current.level + 1));
                    }
                }
            }
        }
        return answer;
    }
}