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

1. 문제

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

코딩테스트 연습 - 단어 변환

 

2. 풀이

• 가장 짧은 변환 과정을 찾으므로 BFS를 사용해 풀이한다.
• 두 개의 단어가 주어졌을 때, 하나의 단어를 다른 단어로 변환할 수 있는지(다른 알파벳의 갯수가 1개인지)를 판별하는 함수 isChangeOk()를 구현한다.
• 처음 시작하는 단어인 begin와 단어 후보들(words) 중 바꿀 수 있는 단어는 모두 큐에 넣는다.
  • 큐의 크기가 0이면 바꿀 수 없는 단어가 없으므로 0을 반환한다.
• 단어 변환을 계속해가며 타겟 단어가 나오는지 확인한다.

 

3. 코드

 

import java.util.Arrays;
import java.util.LinkedList; 
import java.util.Queue; 

class Solution {
    
    int max = 260;
    
    public boolean isChangeOk(String now, String word){ // 바꿀 수 있는 단어인지 확인
        int wrongCnt = 0;
        
        for(int i = 0; i < now.length(); i++){
            if(now.charAt(i) != word.charAt(i)) wrongCnt++;
            if(wrongCnt >= 2) break;
        }
        return wrongCnt == 1 ? true : false;
    }
    
    public int bfs(String target, String[] words, Queue<String> q){
        if(q.isEmpty() == true) return 0; // 될 수 없는 경우
        boolean[] visited = new boolean[words.length];
        
        int cnt = 0;
        String now = "";
        while(!q.isEmpty()){
            int qSize = q.size();
            cnt++; 
            
            for(int j = 0; j < qSize; j++){
                now = q.poll();
            
                if(now.equals(target)) break;
            
                for(int i = 0; i < words.length; i++){
                    if(!visited[i] && isChangeOk(now, words[i]) == true){
                        visited[i] = true;
                        q.add(words[i]);
                    }
                }
            }
            
            if(now.equals(target)) break;
        }
        
        return now.equals(target) ? cnt : 0;
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 300;
        
        Queue<String> q = new LinkedList<>();
        
        // begin 단어에서 변환 가능한 단어 큐에 넣음
        for(int i = 0; i < words.length; i++){
            if(isChangeOk(begin, words[i]) == true){
                q.add(words[i]);
            }
        }
        
        answer = bfs(target, words, q);
        
        return answer;
    }
}