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

제약 사항

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

---

풀이과정

1. words에 있는 단어를 몇번째로 방문했는지 기록하기 위해 HashMap에 저장합니다.
   ( + 동시에 words 배열에 target 있는지 확인한다 -> target 없으면 변환할 수 없으므로 0을 반환합니다.)
2. 최소로 방문해서 target을 만들어야 하므로 bfs를 이용합니다.
3. Queue에 begin을 넣어 bfs 탐색을 시작
4. for문을 사용해 words 배열 안의 단어들을 조사하는데,
   아직 방문한 적이 없고 현재 단어와 알파벳 한 개만 다른 단어는 Queue에 넣습니다.
5. 4번 과정과 동시에, HashMap에 그 단어를 몇 번째 방문하는지 업데이트합니다.
6. while문을 돌면서 target단어가 될 때까지 4,5 과정을 반복하고, 몇 번째로 방문한 단어인지 반환합니다.
7. 만약 Queue가 빌 때까지 target단어가 완성되지 않는다면, 변환할 수 없는 것으로 보고 0을 반환합니다.

---

전체 코드

import java.util.*;
class Solution {
    static Map<String, Integer> map = new HashMap<>(); //몇번째 방문했는지.
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        boolean wordIn=false;
        for(int i=0;i<words.length;i++){
            map.put(words[i],0);
            if(words[i]==target) wordIn=true;
        }
        map.put(begin,0); //begin문자도 0번째 방문했다는걸 불러오기 위해 map에 추가.
        
        if(wordIn) return 0; //target 단어가 words 안에 없으면 0반환.
        
        answer = bfs(begin,target,words);
        
        return answer;
    }
    private int bfs(String begin, String target, String[] words){
        Queue<String> q = new LinkedList<>();
        q.add(begin); //시작점
        
        while(!q.isEmpty()){
            String now = q.poll();
            
            //target단어와 같아지면 종료
            if(now.equals(target)){
                return map.get(now); //몇번째로 now를 방문했는지 반환.
            }
            
            for(int i=0;i<words.length;i++){
                //아직 방문한적 없고 현재 단어와 알파벳 한개만 다를 경우
                if(map.get(words[i])==0 && possible(now,words[i])){
                    q.add(words[i]);
                    map.put(words[i],map.get(now)+1); //몇번째 단계인지 map에 저장.
                }
            }
        }
        return 0; //변환이 안되면 0반환.
    }
    //a와 b가 한개의 알파벳만 다른지 확인.
    private boolean possible(String a, String b){
        //같은 문자열은 안됨
        if(a.equals(b)) return false;
        
        int diff=0;//다른 문자 개수
        for(int i=0;i<a.length();i++){
            if(a.charAt(i)!=b.charAt(i))
                diff++;
            //다른 문자 개수가 2이상이면 false 리턴.
            if(diff>1)
                return false;
        }
        return true;
    }
}