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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

---

문제 개요

두 개의 단어 begin, target과 단어 집합 words가 주어집니다. 단어 변환 규칙은 다음과 같습니다.

1. 한 번에 하나의 알파벳만 바꿀 수 있습니다.
2. 변환 과정에서의 단어는 words에 포함되어야 합니다.

목표는 begin을 시작으로 target으로 변환하는 최소 변환 단계를 찾는 것입니다. 변환할 수 없는 경우 0을 반환합니다.

문제 분석

1. 단어 하나씩 알파벳 하나만 바꿔 target에 도달해야 합니다.
2. 각 단어가 words에 포함된 단어인지 확인해야 하며, 최단 경로를 찾기 위해 BFS(너비 우선 탐색)를 사용합니다.
3. target이 words에 없으면 바로 0을 반환할 수 있습니다.

접근 방법

1. words에 target이 포함되지 않으면 바로 0을 반환합니다.
2. begin을 시작으로 BFS를 통해 단어를 한 단계씩 변환하며 target에 도달할 때까지 탐색합니다.
3. 각 단어를 비교해 알파벳 하나만 다를 경우 다음 탐색 대상으로 추가합니다.

 

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {        
        int answer = 0;
        
        // words에 target이 없으면 0을 반환
        if (Arrays.asList(words).contains(target)) {
            answer = bfs(begin, target, words);
        }
        
        return answer;
    }
    
    // BFS를 이용해 최소 변환 단계를 찾는 함수
    public int bfs(String begin, String target, String[] words) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(begin, 0));
        
        // 큐가 빌 때까지 탐색
        while (!q.isEmpty()) {
            Node cur = q.poll();
            
            // target 단어에 도달하면 변환 횟수 반환
            if (target.equals(cur.s)) return cur.cnt;
            
            // words 배열 내 단어들과 비교하여 변환 가능한 단어를 큐에 추가
            for (String word : words) {
                if (diff(cur.s, word)) {
                    q.add(new Node(word, cur.cnt + 1));
                }
            }
        }
        
        return 0; // target에 도달하지 못한 경우
    }
    
    // 두 단어가 변환 가능한지 체크하는 함수 (한 글자만 다를 경우 true 반환)
    public boolean diff(String s, String word) {
        int cnt = 0;
        
        for (int i = 0; i < word.length(); i++) {
            if (s.charAt(i) != word.charAt(i)) cnt++;
            if (cnt > 1) return false;  // 두 글자 이상 다르면 false 반환
        }
        
        return true;  // 한 글자만 다를 경우 true 반환
    }
    
    // Node 클래스: 변환 과정에서 현재 단어와 변환 횟수 저장
    class Node {
        String s;
        int cnt;
        
        public Node(String s, int cnt) {
            this.s = s;
            this.cnt = cnt;
        }
    }
}