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

문제 소개

 

오늘 풀었던 프로그래머스 - 단어 변환 문제를 정리합니다.

이 문제는 주어진 단어 집합을 이용해, begin 단어를 target 단어로 변환하는 가장 짧은 경로(최소 단계)를 구하는 문제입니다.

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

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. BFS를 사용하여 가장 짧은 변환 과정을 탐색합니다.
2. 변환 가능한 단어는, 단 한 글자만 다르고 words 집합에 있는 단어여야 합니다.
3. 방문한 단어는 다시 방문하지 않도록 관리(visited)합니다.

---

해결 과정 및 코드

핵심 아이디어

1. Queue를 사용하여 현재 단어와 변환 깊이를 함께 저장하고 탐색합니다.
2. 현재 단어에서 변환할 수 있는 단어를 찾으면, 그 단어를 큐에 넣고 depth를 +1 증가시킵니다.
3. target에 도달하면, 그때의 depth를 반환합니다.
4. 끝까지 찾아도 target을 찾지 못하면 0을 반환합니다.

코드

시간 복잡도 : O(N² × L)

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
    	// 애초에 target이 word에 있는지 확인
        if (!Arrays.asList(words).contains(target)) {
            return 0;
        }

        ArrayDeque<Word> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[words.length];
        queue.add(new Word(begin, 0));

        while (!queue.isEmpty()) {
            Word current = queue.poll();
			// 현재 단어와 target 비교
            if (current.word.equals(target)) {
                return current.depth;
            }
			
            // 변환 가능한 단어 탐색
            for (int i = 0; i < words.length; i++) {
                if (!visited[i] && canConvert(current.word, words[i])) {
                    visited[i] = true;
                    queue.add(new Word(words[i], current.depth + 1));
                }
            }
        }

        return 0;
    }

    private boolean canConvert(String a, String b) {
        int diffCount = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diffCount++;
            }
            if (diffCount > 1) {
                return false;
            }
        }
        return diffCount == 1; // 중복되는 단어는 없어서 diffCount = 0은 없다
    }

    static class Word {
        String word;
        int depth;

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