알고리즘 / Java / 프로그래머스 - 단어 변환

 

프로그래머스 - 단어 변환

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

문제 해설

Word 객체를 만들면 쉽게 해결할 수 있습니다.

Word 객체는 다음 정보를 가지고 있습니다.

    class Word {
    	//현재 단계의 단어
        private String currentWord;
        //몇번 바꿨는지
        private int count;
        //어떤 경로를 거쳐 왔는지
        private boolean[] isVisits;

        public Word(String currentWord, int count, boolean[] isVisits) {
            this.currentWord = currentWord;
            this.count = count;
            this.isVisits = isVisits;
        }
    }

위의 객체를 que에 넣고 하나씩 꺼내어 검사하는 너비우선탐색 방법으로 해결하면 됩니다.

 

 

해답 코드

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

public class Solution {
    class Word {
        private String currentWord;
        private int count;
        private boolean[] isVisits;

        public Word(String currentWord, int count, boolean[] isVisits) {
            this.currentWord = currentWord;
            this.count = count;
            this.isVisits = isVisits;
        }
    }

    public int solution(String begin, String target, String[] words) {
        Queue<Word> que = new LinkedList<>();
        //que를 생성하고 begin에서 바꿀수 있는 단어를 모두 que에 넣습니다.
        for (int i = 0; i < words.length; i++) {
            if (canChange(begin, words[i])) {
                boolean[] isVisit = new boolean[words.length];
                isVisit[i] = true;
                que.offer(new Word(words[i], 1, isVisit));
            }
        }

        //que를 돌면서 너비우선탐색
        while (!que.isEmpty()) {
            Word word = que.poll();
            if (word.currentWord.equals(target)) {
                return word.count;
            }

            for (int i = 0; i < words.length; i++) {
                if (!word.isVisits[i] && canChange(word.currentWord, words[i])) {
                    boolean[] isVisit = word.isVisits;
                    isVisit[i] = true;
                    que.offer(new Word(words[i], word.count + 1, isVisit));
                }
            }
        }
        return 0;
    }

    private boolean canChange(String word, String toChange) {
        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) != toChange.charAt(i)) {
                count++;
            }
            if (count > 1) {
                return false;
            }
        }
        return count == 1;
    }
}