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

---

📄 문제

단어 변환

 

💡 풀이

BFS(너비 우선 탐색) 알고리즘을 사용하여 "begin" 문자열에서 "target" 문자열로 변환하는데 필요한 최소 단계 수를 계산합니다.

 

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0; // 최소 단계 수를 저장할 변수
        boolean[] visited = new boolean[words.length]; // 단어 방문 여부를 추적하는 배열
        Queue<String> queue = new LinkedList<>(); // BFS 탐색을 위한 큐

        queue.offer(begin); // 시작 단어를 큐에 추가

        while (!queue.isEmpty()) { // 큐가 비어있지 않은 동안 반복
            int size = queue.size(); // 현재 레벨의 큐 크기를 저장

            for (int i = 0; i < size; i++) {
                String current = queue.poll(); // 큐에서 현재 단어 추출

                if (current.equals(target)) { // 현재 단어가 목표 단어인 경우
                    return answer; // 최소 단계 수 반환
                }

                for (int j = 0; j < words.length; j++) {
                    if (!visited[j] && canTransform(current, words[j])) {
                        // 단어 방문 여부 확인 및 변환 가능한 경우
                        visited[j] = true; // 단어를 방문으로 표시
                        queue.offer(words[j]); // 큐에 추가
                    }
                }
            }

            answer++; // 현재 레벨의 모든 단어를 처리하고 단계 증가
        }

        return 0; // 변환할 수 없는 경우
    }

    private boolean canTransform(String from, String to) {
        int diffCount = 0; // 문자 차이를 나타낼 변수 초기화

        for (int i = 0; i < from.length(); i++) {
            if (from.charAt(i) != to.charAt(i)) {
                diffCount++; // 다른 문자가 발견될 때마다 증가
            }

            if (diffCount > 1) {
                return false; // 문자 차이가 1을 초과하면 변환 불가능
            }
        }

        return diffCount == 1; // 문자 차이가 1이면 변환 가능, 그 외엔 불가능
    }
}