99클럽 코테 스터디 33일차 TIL + 단어 변환 (BFS)

 

 

 

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 프로그래머스 - 단어 변환 (문제 링크)
• BFS (너비 우선 탐색)
• 그래프 탐색

 

---

 

문제 설명

두 개의 단어 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으로 변환할 수 있는지를 찾는 것입니다. 변환할 수 없는 경우에는 0을 반환해야 합니다.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0을 반환합니다.

 

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

---

 

문제 접근

이 문제는 BFS(너비 우선 탐색)를 사용하여 해결할 수 있습니다.

BFS는 최단 경로를 찾는 데 유용한 알고리즘으로, 모든 가능성을 동일한 우선순위로 탐색하여 가장 짧은 변환 과정을 찾을 수 있습니다.

1. 먼저 begin 단어에서 시작하여, 한 번에 한 개의 알파벳만 다른 단어로 변환할 수 있는 모든 가능성을 탐색합니다.
2. 변환된 단어가 words에 포함되어 있고, 아직 방문하지 않았다면, 해당 단어를 큐에 추가하여 다음 탐색을 진행합니다.
3. 이 과정을 반복하여 target에 도달하면 그때의 변환 단계를 반환합니다.

 

 

풀이 - Java 코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {

        List<String> wordList = Arrays.asList(words);

        if (!wordList.contains(target)) {
            return 0;
        }

        Queue<WordNode> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.offer(new WordNode(begin, 0));
        visited.add(begin);

        while (!queue.isEmpty()) {
            WordNode node = queue.poll();
            String word = node.word;
            int level = node.level;

            if (word.equals(target)) {
                return level;
            }

            for (String w : wordList) {
                if (!visited.contains(w) && canTrans(word, w)) {
                    queue.offer(new WordNode(w, level + 1));
                    visited.add(w);
                }
            }
        }

        return 0;
    }

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

    class WordNode {
        private String word;
        private int level;
        WordNode(String word, int level) {
            this.word = word;
            this.level = level;
        }
    }
}

풀이 설명

1. 초기화
   • begin에서 시작하여 BFS 탐색을 위해 큐를 초기화합니다. 방문한 단어는 다시 방문하지 않도록 visited 집합을 사용합니다.
   • 만약 target이 words 리스트에 포함되지 않으면, 변환할 수 없으므로 0을 반환합니다.
2. BFS 탐색
   • 큐에서 단어를 하나씩 꺼내어, target과 동일한지 확인합니다. 동일하다면 변환 단계(level)를 반환합니다.
   • 현재 단어에서 한 글자만 다른 단어로 변환할 수 있는지 확인하고, 변환 가능한 단어를 큐에 추가합니다. 이때, 이미 방문한 단어는 큐에 추가하지 않습니다.
3. 단어 변환 가능 여부 확인
   • 두 단어를 비교하여 한 글자만 다른지 확인하는 canTrans 메서드를 사용하여, 변환 가능성을 검사합니다.
4. 결과 반환
   • BFS를 통해 target에 도달하지 못한 경우, 변환할 수 없으므로 0을 반환합니다.

 

 

---

 

 

마무리하며

BFS는 모든 경로를 동일한 우선순위로 탐색하기 때문에, 변환 과정을 단계별로 정확하게 추적할 수 있습니다. 이번 풀이에서는 큐를 사용하여 변환 과정을 효율적으로 관리하고, 한 글자씩 다른 단어로 변환하는 로직을 구현했습니다.