DFS/BFS>단어 변환[프로그래머스-JAVA]

📝문제

📝알고리즘

//큐에 begin을 넣음
//큐가 빌때까지 다음을 반복
//큐에 있는 단어만큼
//큐에 있는 단어를 꺼내서 target과 같으면 단계의 수 answer를 반환
//같지 않으면
//words에 있는 단어들 중 아직 방문하지 않았고 한 개의 알파벳만 바꿔서 될 수 있는 단어를 방문해서 기록하고 그 단어를 큐에 넣음
//단계 수를 늘림
//큐가 모두 비었으면 target이 될 수 없으므로 0 반환
//입력받은 두 단어가 한 개의 알파벳만 다를 때 true를 반환하는 함수 작성

📝구현

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean[] visited =new boolean[words.length];
        Queue<String> queue=new LinkedList<>();
        queue.offer(begin);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0; i<size;i++){
                String now=queue.poll();
                if(now.equals(target)){
                    return answer;
                }
                for(int j=0; j<words.length;j++){
                    if(!visited[j] && canTransform(now, words[j])){
                        visited[j]=true;
                        queue.offer(words[j]);
                    }
                }
            }
            answer++;
        }
        return 0;
    }
    
    private boolean canTransform(String word1, String word2){
        int diff=0;
        for(int i=0; i<word1.length();i++){
            if(word1.charAt(i)!=word2.charAt(i)){
                diff++;
            }
            
        }
        if(diff==1){
            return true;
        }
        else{
            return false;
        }
    }
}

📌기록하고 싶은 내용

다른 사람들의 풀이를 보니 DFS로 푸는 방법도 있던데 DFS로도 다음에 한 번 풀어보면 좋을 것 같다..!