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

📖 문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

✍ 입력

📄 출력

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

✅ 코드

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<Word> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[words.length];
        queue.offer(new Word(begin, 0));

        while (!queue.isEmpty()) {
            Word currentWord = queue.poll();

            if(currentWord.word.equals(target)) {
                return currentWord.depth;
            }

            for(int i=0; i<words.length; i++) {
                if(!visited[i] && isDiffChar(currentWord.word, words[i])) {
                    visited[i] = true;
                    queue.offer(new Word(words[i], currentWord.depth + 1));
                }
            }

        }

        return 0;
    }

	// 다른 알파벳의 갯수가 1개인지 체크
    private static boolean isDiffChar(String fst, String sec) {
        int diffCount = 0;
        for(int i=0; i<fst.length(); i++) {
            if(fst.charAt(i) != sec.charAt(i)) {
                diffCount++;
            }
        }

        return diffCount == 1;
    }

	// 단어 정보와 깊이 정보를 저장하기 위해 Word 클래스를 생성
    private static class Word {
        String word;
        int depth;

        Word(String word, int depth) {
            this.word = word;
            this.depth = depth;
        }
    }
}

🧩 코드풀이

• 해당 문제는 BFS 알고리즘으로 풀이를 진행했습니다.

1. while문을 이용하여 Queue의 값이 비어있을 때까지 반복을 진행합니다.
2. words 배열의 각 값을 반복하며 다른 알파벳의 갯수가 1개인 값들을 queue에 저장해줍니다.
3. 위와 같은 내용을 반복하며 queue의 word 값이 목표로 한 단어와 동일해졌을 때 해당 depth를 return 해줍니다. 만약 동일한 값이 없으면 0을 리턴합니다.