[프로그래머스/Java] 단어 변환

문제

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

---

문제풀이 방법

1. begin을 큐에 추가한다
2. 큐가 빌 때까지 탐색 반복
   -> begin 이 target 과 같으면 cnt(변환단계 수) 반환
3. 인접 단어 탐색
   -> 아직 방문하지 않았고, 현재 단어와 한글자만 차이나는 단어 탐색
   -> 방문 표시, 변환단계 증가, 새로운 상태를 큐에 추가
4. 목표 단어를 찾지 못한 경우 return 0

---

나의 코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<WordState> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[words.length];
        
        queue.add(new WordState(0, begin));
        
        while(!queue.isEmpty()){
            WordState cur = queue.remove();
            if(cur.word.equals(target)) return cur.cnt;
            
            for(int i = 0; i < words.length; i++){
                if(!visited[i] && getDiffCount(cur.word, words[i]) == 1){
                    visited[i] = true;
                    queue.add(new WordState(cur.cnt +1, words[i]));
                }
            }
        }
        return 0;
    }
    
    int getDiffCount(String word, String target){
        int diffCount = 0;
        for(int i = 0; i < word.length(); i++){
            if(word.charAt(i) != target.charAt(i)) diffCount++;
        }
        return diffCount;
    }
    
    class WordState{
        int cnt;
        String word;
        
        WordState(int cnt, String word){
            this.cnt = cnt;
            this.word = word;
        }
    }
}