1. 문제 개요

문제:
주어진 시작 단어 begin에서 목표 단어 target으로 변환하는 가장 짧은 단계를 찾아야 합니다.
변환은 다음 두 가지 조건을 만족해야 합니다:
한 번에 한 개의 알파벳만 변경 가능.
변환된 단어는 반드시 words 목록에 존재해야 함.

목표: 최소 변환 단계 수를 반환. 변환이 불가능할 경우 0 반환.

2. 문제 접근

초기 조건 확인:
target이 words에 없으면 변환이 불가능하므로 바로 0 반환.

변환 가능성 체크 함수:
두 단어가 한 글자만 다를 때만 변환 가능.
zip을 활용해 두 단어의 각 문자 쌍을 비교하고 다른 문자의 개수를 세어 조건을 확인.

최단 경로 탐색:
변환 과정은 단계별로 진행되므로 BFS(너비 우선 탐색)를 사용하여 최단 경로를 탐색.

BFS 탐색 과정:
시작 단어 begin을 큐에 삽입하고, 변환 단계를 0으로 설정.
큐에서 단어를 하나씩 꺼내며 변환 가능한 단어를 찾고 큐에 추가.
목표 단어 target에 도달하면 변환 단계를 반환.
모든 단어를 탐색해도 도달하지 못하면 0 반환.

3. 구현 코드

import Foundation

func solution(_ begin: String, _ target: String, _ words: [String]) -> Int {
    // target이 words에 없는 경우 바로 반환
    if !words.contains(target) {
        return 0
    }
    
    // 두 단어가 한 글자만 다른지 확인하는 함수
    func isConvertible(_ word1: String, _ word2: String) -> Bool {
        let diffCount = zip(word1, word2).filter { $0 != $1 }.count
        return diffCount == 1
    }
    
    // BFS를 위한 큐와 방문 체크 배열
    var queue: [(String, Int)] = [(begin, 0)]  // (현재 단어, 변환 단계)
    var visited = Set<String>()               // 방문한 단어 기록
    
    // BFS 탐색 시작
    while !queue.isEmpty {
        let (currentWord, steps) = queue.removeFirst()
        
        // target 단어에 도달하면 변환 단계 반환
        if currentWord == target {
            return steps
        }
        
        // 아직 방문하지 않은 단어 중에서 변환 가능한 단어를 큐에 추가
        for word in words where !visited.contains(word) && isConvertible(currentWord, word) {
            visited.insert(word)
            queue.append((word, steps + 1))
        }
    }
    
    // target에 도달하지 못하면 0 반환
    return 0

}

4. 코드 분석

초기 조건 확인:

if !words.contains(target) {
    return 0
}

목표 단어가 words에 없다면 변환이 불가능하므로 바로 0 반환.

변환 가능성 체크 함수:

func isConvertible(_ word1: String, _ word2: String) -> Bool {
    let diffCount = zip(word1, word2).filter { $0 != $1 }.count
    return diffCount == 1
}

zip으로 두 단어의 각 문자를 비교.
다른 문자의 개수가 1이면 변환 가능.

BFS 탐색:

var queue: [(String, Int)] = [(begin, 0)]
var visited = Set<String>()

queue: 현재 단어와 변환 단계를 저장.
visited: 이미 변환한 단어를 기록해 중복 탐색 방지.

큐를 활용한 탐색:

while !queue.isEmpty {
    let (currentWord, steps) = queue.removeFirst()
    if currentWord == target {
        return steps
    }
    for word in words where !visited.contains(word) && isConvertible(currentWord, word) {
        visited.insert(word)
        queue.append((word, steps + 1))
    }
}

큐에서 단어를 꺼내, 변환 가능한 단어를 탐색.
변환 가능한 단어는 queue에 추가하고 방문 처리.

결과 반환:
목표 단어에 도달하면 변환 단계 반환.
도달하지 못하면 0 반환.

5. 시간 복잡도

단어 길이: L (최대 10)
단어 개수: N (최대 50)
BFS 탐색:
각 단어에 대해 최대 O(L×N)의 연산 수행.
총 시간 복잡도:
O(N^2×L), 최악의 경우 N^2번 탐색.

6. 학습한 점

BFS 활용:
너비 우선 탐색(BFS)은 최단 경로 탐색에 효과적임.
큐를 활용해 단계를 관리하며 탐색 가능.

문자열 비교:
zip과 filter를 활용해 문자열 비교를 간단히 구현.

방문 체크:
Set을 사용해 중복 탐색을 방지하여 효율성을 높임.