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

코딩테스트 연습 - 단어 변환 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

최단 변환의 수를 구해야 하는 문제이므로 BFS를 통해 문제를 해결하고자 하였습니다.

코드

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        Queue<Word> queue = new LinkedList<>();
        queue.offer(new Word(begin,0));
        while(!queue.isEmpty()){
            Word word = queue.poll();
            if(target.equals(word.value)) return word.count;
            for(int i=0;i<words.length;i++){
                if(!visited[i] && isConvertable(word.value,words[i])){
                    visited[i] = true;
                    queue.offer(new Word(words[i],word.count+1));
                } 
            }
        }
        return 0;
    }
    boolean isConvertable(String A, String B){
        int difference = 0;
        for(int j=0;j<A.length();j++){
            if(A.charAt(j)!=B.charAt(j)) difference++;
            if(difference>1) return false;
        }
        return true;
    }
    class Word{
        String value;
        int count;
        Word(String value, int count){
            this.value = value;
            this.count = count;
        }
    }
} 

 

테스트를 통과하는 코드를 작성하였습니다.

변환할 수 있는 문자를 판단한 후 Queue에 삽입하여 다음 변환을 대기합니다.

변환 시도의 수를 반환하기 위해서는 해당 문자가 몇번 변환을 거쳐간 문자인지 기억할 필요가 있습니다.

클래스 Word를 선언하여 문자열과 변환 횟수를 함께 저장함으로서 이를 해결하고자 하였습니다.