프로그래머스 Lv.3: 단어 변환 - Swift 풀이

문제 설명

프로그래머스

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

풀이 과정

주어진 단어를 한 번에 한 글자씩 변경해가며 목표 단어로 변환하는 최단 경로를 찾는 문제입니다.
BFS(너비 우선 탐색)를 사용하면 최단 변환 횟수를 보장할 수 있습니다.

1. 최단 경로 탐색: BFS는 레벨별로 탐색하기 때문에 목표 단어를 처음 만나는 순간이 최소 단계입니다.
2. 사이클 방지: 방문 기록(visited)을 통해 이미 처리한 단어를 재방문하지 않습니다.

→ 각 단어를 노드로, 한 글자 차이를 간선이라고 생각하면 BFS 적용도 자연스럽습니다.

정답 코드

import Foundation

// Deque 구현
class Deque<T>{
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    // 생성자
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    // words에 target이 없으면 즉시 0 반환해서 종료
    guard let _ = words.firstIndex(of: target) else {
        return 0
    }
            
    // a와 b가 1 글자만 다를 때 true 반환
    func isOneLetterDifferent(_ a: String, _ b: String) -> Bool {
        if a.count != b.count {
            return false
        }

        let aChars = Array(a)
        let bChars = Array(b)
        var diffCount = 0

        for i in 0..<aChars.count {
            if aChars[i] != bChars[i] {
                diffCount += 1
                // 2개 이상 다르면 false 반환
                if diffCount > 1 {
                    return false
                }
            }
        }

        return diffCount == 1
    }
        
    // 너비 우선 탐색으로 최단 거리 찾기
    func BFS() -> Int {
        // (현재 단어, 변환 횟수) 구조의 덱 생성
        let queue: Deque<(String, Int)> = Deque([(begin, 0)])
        // 단어 방문 여부
        var visited = Array(repeating: false, count: words.count)
        
        // 큐가 비어있지 않으면 반복
        while !queue.isEmpty {
            // 첫번째 요소 pop
            let (now, step) = queue.popFirst()
            // 현재 단어가 타겟이면
            if now == target {
                // 변환 횟수 반환해서 종료
                return step
            }
            // 단어 개수만큼 반복
            for i in 0..<words.count {
                // 현재 글자랑 i번째 단어랑 한 글자 차이나고, i번째 단어 아직 방문하지 않은 거면
                if isOneLetterDifferent(now, words[i]) && !visited[i] {
                    // 방문 처리
                    visited[i] = true
                    // 큐에 (i번째 단어, 방문횟수 +1한 값) 넣는다
                    queue.pushLast((words[i], step + 1))
                }
            }
        }
        
        // 여기까지 왔으면 타겟 단어가 있었는데도 타겟 단어까지 도달할 수 있는 경로가 없었다는 뜻
        // 이 경우는 변환이 불가능한 거니까 0을 반환한다
        return 0
    }
    
    return BFS()
}

[예제 실행 과정]
입력: begin = "hit", target = "cog", words = ["hot","dot","dog","lot","log","cog"]

1. BFS 시작: 큐에 ("hit", 0) 추가
2. 1단계: "hit" → "hot" (steps=1)
3. 2단계: "hot" → ["dot", "lot"] (steps=2)
4. 3단계: "dot" → "dog", / "lot" → "log" (steps=3)
5. 4단계: "dog" → "cog" (steps=4) → 목표 도달

이상입니다.