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

문제 : 단어 변환 - 프로그래머스

풀이과정

문제에서 주어진 조건은 다음과 같다.

• 한 번에 한 개의 알파벳만 바꿀 수 있다.
• words에 있는 단어로만 변환할 수 있다.

이 조건으로부터 우리는 매 턴 마다 현재 단어에서 바뀔 수 있는 단어들을 찾아낼 수 있다.

예를 들어, 문제에서 주어진 예시를 보면, begin 으로 "hit"가 주어졌으며, words로는 ["hot", "dot", "dog", "lot", "log", "cog"]가 주어졌다. "hit"에서 변화할 수 있는 알파벳은 'h', 'i', 't' 셋 중 하나이다.

여기서 words에 있는 단어들로부터, 'h', 'i', 't'가 각각 어떤 알파벳으로 변할 수 있는지 알 수 있는데, words에 속한 단어들의 각 알파벳을 보면, 처음 주어진 단어 "hit"는 다음과 같은 변화가 가능하다.

• 'h' → hot, dot ( dog ), lot ( log ), cog → h, d, l, c
• 'i' → hot, dot ( dog ), lot ( log ), cog → o
• 't' → hot, dot ( dog ), lot ( log ), cog → t, g

즉, 처음 주어진 단어 "hit"는 한 번의 변환을 통해 다음과 같은 단어들로 변환될 수 있다.

• hit → hit, dit, lit, cit, hot, hit, hig

이 후보들 중 words에 속하는 단어는 hot 뿐이다. 따라서, hit는 hot으로만 변환이 가능하다.

이 때, 변환 가능한 단어가 하나가 아니라 여러 개 일 수도 있는데, 이런 경우 변환 가능한 단어를 모두 큐에 넣은 후 BFS 방식으로 진행하면 된다.

이러한 과정을 words에 더이상 사용하지 않은 단어가 없을 때 까지(또는 target과 같은 단어가 나타났을 때 까지) 반복하면 begin → target까지 변환을 위해 몇 단계를 거쳐야 하는지 알 수 있다. 만일 words에 더이상 사용하지 않은 단어가 존재하지 않음에도 begin 단어가 target 단어까지 변환이 완료되지 않았다면, 이는 begin 단어는 주어진 words를 통해서 target까지 변환될 수 없음을 의미한다.

예시

문제에서 주어진 예시에 대한 전체 진행 과정은 다음과 같다.

[count 0]
queue : "hit"
words : "hot", "dot", "dog", "lot", "log", "cog"
→ 첫 번째 changable Strings : "hit", "dit", "lit", "cit", "hot", "hog"
→ 이들 중 words에 속한 Strings : "hot"

[count 1]
queue : "hot"
words : "dot", "dog", "lot", "log", "cog"
→ 두 번째 changable Strings : "dot", "lot", "cot", "hot", "hog"
→ 이들 중 words에 속한 String : "dot", "lot"

[count 2]
queue : "dot", "lot"
words : "dog", "log", "cog"
→ 세 번째 changable Strings : "lot", "cot", "dog", "dot", "lot", "cot", "log"
→ 이들 중 words에 속한 String : "dog", "log"

[count 3]
queue: "dog", "log"
words: "cog"
→ 네 번째 changable Strings : "cog"
→ 이들 중 words에 속한 String : "cog"

[count 4]
queue : "cog"
words : [empty]
→ queue.poll() 과 target이 일치. return count. END.

소스코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<String> currentPossibleStrings = new LinkedList<>();
        currentPossibleStrings.offer(begin);

        Set<String> availableStrings = new HashSet<>(Arrays.asList(words));

        int count = 0;
        while (!currentPossibleStrings.isEmpty()) {
            int size = currentPossibleStrings.size();

            for (int i = 0; i < size; i++) {
                String currentString = currentPossibleStrings.poll();
                if (currentString.equals(target)) {
                    return count;
                }

                currentPossibleStrings.addAll(convertString(currentString, availableStrings));
            }
            count++;
        }
        return 0; // impossible to convert
    }

    private List<String> convertString(String currentString, Set<String> availableStrings) {
        List<String> result = new LinkedList<>();
        int size = currentString.length();

        for (int i = 0; i < size; i++) {
            char[] chars = currentString.toCharArray();

            Iterator<String> iter = availableStrings.iterator();
            Set<Character> changeableCharacters = new HashSet<>();
            while (iter.hasNext()) {
                changeableCharacters.add(iter.next().charAt(i));
            }

            for (char ch : changeableCharacters) {
                chars[i] = ch;
                String convertedString = new String(chars);
                if (availableStrings.remove(convertedString)) {
                    result.add(convertedString);
                }
            }
        }
        return result;
    }
}