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

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

프로그래머스

---

문제 풀이

BFS로 풀이

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        
        Queue<Word> q = new LinkedList<>();
        q.add(new Word(begin, 0));
        
        while(!q.isEmpty()) {
            Word nowWord = q.poll();
            
            if(nowWord.word.equals(target)) {
                return nowWord.depth;
            }
            
            for(int i=0; i<words.length; i++) {
                if(!visited[i] && diffOneWord(nowWord.word, words[i])) {
                    // 방문하지 않았고, 한글자만 다르다면
                    q.add(new Word(words[i], nowWord.depth + 1));
                    visited[i] = true;
                }
            }
        }
        
        return 0;
    }
    
    private boolean diffOneWord(String str, String target) {
        int diff = 0;
        
        for(int i=0; i<target.length(); i++) {
            if(str.charAt(i) != target.charAt(i)) {
                diff++;
            }
        }
        
        if(diff == 1) {
            return true;
        } else {
            return false;
        }
    }
    
    
    class Word {
        String word;
        int depth;
        
        public Word(String word, int depth) {
            this.word = word;
            this.depth = depth;
        }
    }
}