프로그래머스 - 단어변환 - BFS - Java

1. 문제

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

2. 풀이

최단거리 이므로 BFS

✨핵심 Point

1. words배열에 target이 없으면 일찍 return 0을 해줘야 한다. 어떻게 해도 안만들어지기 때문.

2. 방문 체크.
   안해줘도 되지만 해주는게 맞는거같다. hit -> hot -> hit....계속해서 무한 루프에 빠질 수 있기 때문이다.

3. 두 단어는 하나의 문자만 다를 때 변환될 수 있다.
   어려운 한방 로직을 생각하지 말고 생각이 나지 않을때는 단순한 풀이법이 도움이 된다.
   👍두 배열을 돌면서 같지 않은 단어의 개수를 세주는 간단한 로직!

        char bfArr[] = bf.toCharArray();
        char afArr[] = af.toCharArray();
        int count = 0;
        for(int i = 0; i < bf.length(); i++){
            if(bfArr[i] != afArr[i]){
                count++;
            }    
        }

3. 전체 코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        ArrayList<String> wordList = new ArrayList<>(Arrays.asList(words));
        if(!wordList.contains(target)){
            return 0;
        }
        
        Queue<String> qS = new LinkedList<>();
        Queue<Integer> qC = new LinkedList<>();
        boolean visit[] = new boolean[words.length];
        
        qS.add(begin);
        qC.add(0);
        
        while(!qS.isEmpty()){
            String checkS = qS.poll();
            int checkC = qC.poll();
            
            if(checkS.equals(target)){
                answer = checkC;
                break;
            }
            
            for(int j = 0; j < words.length; j++){
                if(!visit[j] && checkChange(checkS, words[j])){
                    visit[j] = true;
                    qS.add(words[j]);
                    qC.add(checkC + 1);
                }
            }
        }
        return answer;
    }
    
    public boolean checkChange(String bf, String af){
        char bfArr[] = bf.toCharArray();
        char afArr[] = af.toCharArray();
        int count = 0;
        
        for(int i = 0; i < bf.length(); i++){
            if(bfArr[i] != afArr[i]){
                count++;
            }    
        }
        
        return count == 1;
    }
}