[프로그래머스] 단어 변환 - Java(자바)

 

문제 이해

• 한번에 한 알파벳만 바꿀 수 있다.
• 한번에 문자열의 한 알파벳만 바꾸면서 words에 포함된 단어로 변경, target에 최소한의 과정으로 변환 가능한 숫자를 구하여라
• 한번에 한 알파벳만 바꿔서 words에 포함된 문자열을 구하는건 begin 문자열과 한개의 알파벳만 다르다는걸 의미한다.
• bfs 방법으로 최소한의 과정을 구하기로 했다.
• 큐와 방문자 배열을 생성하여 한개의 알파벳만 다른걸 구한다.
• words의 단어가 한개의 알파벳만 다르고 방문한적이 없다면 (여태까지 방문한 횟수 + 1 )을 방문자 배열에 집어 넣는다.

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        int[] visit = new int[words.length];
        Queue<Integer> que = new LinkedList<>();
        int check = 0;
        
        // words 배열 문자열중 한 알파벳만 다를 경우 begin에 다시 넣고 시작
        for(int i = 0; i<words.length; i++){
            if(visit[i] == 0 && diff(begin, words[i]) == 1){
                que.add(i);
                visit[i] = 1;
            }
            
            if(target.equals(words[i])){
                check = 1;
            }
        }
        
        // 변활할 수 없는 경우 0
        if(check == 0) return 0;
        
        while(!que.isEmpty()){
            int idx = que.poll();
            String str = words[idx];
            
            if(str.equals(target)){
                answer = visit[idx];
                break;
            }
            
            for(int i = 0; i<words.length; i++){
                if(visit[i] == 0 && diff(str, words[i]) == 1){
                    que.add(i);
                    visit[i] = visit[idx] + 1;
                }
            }
        }
        
        return answer;
    }
    
    static int diff(String start, String last){
        
        int cnt = 0;
        for(int i = 0; i<last.length(); i++){
            if(start.charAt(i) != last.charAt(i)){
                cnt++;
            }
        }
        
        return cnt;
    }
}