[프로그래머스 알고리즘 고득점 Kit][깊이/너비 우선 탐색(DFS/BFS)][Java] 단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java

프로그래머스

1.  target이 단어 집합에 있나 확인 -> 없어서 틀렸었음

2. 하나가 다르면 바꿀 수 있다를 갈 수 있다고 생각하면 Node끼리의 최단 거리로 생각할 수 있다.

3. bfs에 begin을 넣고 단어 집합에 하나만 다른 단어를 q에 넣고 count를 늘려서 레벨별로 나아간다.

3.1) Node 클래스를 만들어서 count를 같이 보내주면서 노드 하나씩 보는 방법도 있지만 여기서는 
같은 레벨에 있는 단어들을 하나씩 확인하고 다음으로 나아가는 식으로 bfs를 구현했음

import java.util.*;

class Solution {

    public int solution(String begin, String target, String[] words) {
        if(!containsTarget(target, words)) {
            return 0;
        }
        
        return bfs(begin, target, words);
    }

    public int bfs(String begin, String target, String[] words) {
        Queue<String> q = new ArrayDeque<>();
        boolean[] visited = new boolean[words.length];
        
        q.add(begin);
        int count = 0;
        while(!q.isEmpty()) {
            int size = q.size();
            
            for(int i=0; i<size; i++) {
                String curr = q.poll();
                
                if(curr.equals(target)) {
                    return count;
                }
                
                for(int j=0; j<words.length; j++) {
                    if(visited[j]) continue;
                    
                    if(canTransform(curr, words[j])) {
                        q.add(words[j]);
                        visited[j] = true;
                    }
                }
            }
            count++;
        }
        return count;
    }
    
    public boolean containsTarget(String target, String[] words) {
        for(String word : words) {
            if(word.equals(target)) {
                return true;
            }
        }
        return false;
    }
    public boolean canTransform (String u, String v) {
        int diffCount = 0;
        
        for(int i=0; i<u.length(); i++){
            if(u.charAt(i) != v.charAt(i)) {
                diffCount++;
                if(diffCount > 1) {
                    return false;
                }
            }
        }
        return diffCount == 1;
    }
}