프로그래머스 Level 3 – 단어 변환(Java, BFS)

🔤 프로그래머스 Level 3 – 단어 변환(Java, BFS)

이번에 풀어본 문제는 단어(begin → target) 변환 과정에서 최소 단계 수를 구하는 BFS 문제이다.
문제 조건이 흥미로운데, 한 번에 단 하나의 알파벳만 바꿀 수 있고,
그렇게 바꾼 단어가 반드시 words 리스트 안에 있어야 한다.

이 조건 때문에

“그래프 탐색 문제처럼 보이지만, 사실 문자열을 노드로 취급하는 BFS 문제”

로 해석하면 훨씬 쉽게 풀린다.

---

📌 문제 핵심 요약

• 시작 단어: begin
• 목표 단어: target
• 사용할 수 있는 단어 리스트: words[]
• 한 번에 1글자만 변화 가능
• words에 없는 단어로는 이동 불가
• begin → target 까지 도달하는 최소 단계 수 구하기

결국 begin을 시작점으로 두고 words 안의 단어들과 비교하며,
1글자만 다른 단어들로 이동하는 BFS를 수행하면 된다.

---

🧠 핵심 아이디어

✔ BFS로 탐색

각 단어를 노드(node)로 보고,
1글자만 다른 단어들끼리 연결되어 있다고 보면 그래프 구조가 된다.

✔ 한 글자만 다른지 체크

두 단어의 각 자리 문자를 비교해
다른 문자가 정확히 하나일 때만 이동 가능.

✔ 방문 배열을 사용해서 중복 탐색 방지

vist[i] == true면 해당 words[i]는 이미 방문한 것.

✔ 큐에는 (단어, 현재 레벨)을 함께 저장

단계 증가를 쉽게 계산하기 위해 문자열 배열로 함께 넣었다.

---

🧩 Java BFS 코드

 

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        if(!Arrays.asList(words).contains(target)) return 0;
        
        int len = begin.length();
        boolean[] vist = new boolean[words.length];
        
        Queue<String[]> q = new ArrayDeque<>();
        q.add(new String[]{begin, "0"});
        
        while(!q.isEmpty()){
            String[] cur = q.poll();
            String word = cur[0];
            int level = Integer.parseInt(cur[1]);
            
            // 목표 도달
            if(word.equals(target)) return level;
            
            // words 리스트 탐색
            for(int a = 0; a < words.length; a++){
                int cnt = 0;
                
                for(int i = 0; i < len; i++){
                    if(cnt > 1) break;
                    if(word.charAt(i) != words[a].charAt(i)) cnt++;
                }
                
                // 글자 1개만 다르고, 아직 방문하지 않았다면 이동
                if(!vist[a] && cnt == 1) {
                    q.add(new String[]{words[a], String.valueOf(level + 1)});
                    vist[a] = true;
                }
            }
        }
        
        return 0;
    }
}

---

🔍 코드 설명

✔ “target이 words 안에 없으면 정답이 0”

애초에 변환할 수 없기 때문.

✔ BFS 구조

큐에 (단어, 현재까지 변환 횟수)를 저장.

✔ 방문 체크

한 번 방문한 단어는 다시 방문할 필요 없음 → 최단 거리 BFS 보장.

✔ 글자수 비교

서로 다른 문자가 1개이면만 이동 가능.

---

🎯 정리

• BFS를 사용하여 가장 먼저 target에 도달하는 경로가 최소 변환 횟수이다.
• DFS로도 풀 수 있지만 BFS가 최단 거리 문제에서는 정답에 가깝다.
• 문자열 비교를 통해 그래프를 “동적으로” 만들어 탐색한다는 점이 핵심.