Algorithm: 단어 변환

문제 링크

해결한 코드

import Foundation

func solution(_ begin: String, _ target: String, _ words: [String]) -> Int {
    guard words.contains(target) else { return 0 } // 변환할 수 없는 경우 0을 return
    
    // graph 만들기
    var graph: [String:[String]] = [:]
    let allWords = [begin] + words
    
    func isDifferenceOneLetter(_ word1: String, _ word2: String) -> Bool {
        let array1 = Array(word1)
        let array2 = Array(word2)
        var diffCount = 0
        
        for i in 0..<array1.count {
            if array1[i] != array2[i] {
                diffCount += 1
            }
            if diffCount > 1 { return false }
        }
        return diffCount == 1
    }
    
    for i in 0..<allWords.count {
        let word1 = allWords[i]
        for j in 0..<allWords.count {
            let word2 = allWords[j]
            
            if isDifferenceOneLetter(word1, word2) {
                graph[word1, default: []].append(word2)
            }
        }
    }
    
    // BFS
    func bfs(_ begin: String, _ target: String, _ graph: [String:[String]]) -> Int {
        var visited: Set<String> = []
        var queue: [(word: String, depth: Int)] = []
        queue.append((begin, 0))
        visited.insert(begin)
        
        while !queue.isEmpty {
            let current = queue.removeFirst()
            let word = current.word
            let depth = current.depth
            
            if word == target {
                return depth
            }
            
            for nextWord in graph[word, default: []] {
                guard !visited.contains(nextWord) else { continue }
                visited.insert(nextWord)
                queue.append((nextWord, depth + 1))
            }
        }
        return 0
    }
    
    return bfs(begin, target, graph)
}

개선 가능한 점:
Queue를 일반 Array로 구현하면, .removeFirst()를 수행할 때 O(N)의 시간복잡도를 가지게 된다.
Array는 앞의 요소가 사라진 만큼 뒤의 요소를 모두 한 칸씩 이동시키기 때문이다.
이를 Queue를 직접 구현함으로써 해결할 수 있다.

Deque

    // deque
    struct Deque<T> {
        private var array: Array<T?> = []
        private var head: Int = 0
        
        var isEmpty: Bool {
            return count == 0
        }
        
        var count: Int {
            return array.count - head
        }
        
        // Deque 앞에 추가
        mutating func appendLeft(_ element: T) {
            if head > 0 {
                head -= 1
                array[head] = element
            } else {
                array.insert(element, at: 0)
            }
        }
        
        // Deque 뒤에 추가
        mutating func append(_ element: T) {
            array.append(element)
        }
        
        // Deque 앞에서 출력
        mutating func popLeft() -> T? {
            guard head < array.count, let element = array[head] else { return nil }
            array[head] = nil // Array에서 원소를 제거하는 것이 아니라, nil로 놓음 (Array 크기 변화 X)
            head += 1
            optimizer() // Array 크기 조정
            return element
        }
        
        // Deque 뒤에서 출력
        mutating func pop() -> T? {
            return array.popLast() ?? nil
        }
        
        // 필요 시, Array가 일정 크기를 넘지 않도록 하는 Helper
        mutating func optimizer() {
            if head > 50 && head > (array.count / 2) {
                array.removeFirst(head)
                head = 0
            }
        }
    }

What I've learned:

Ref.

• [BarkingDog] [실전 알고리즘] 0x09강 - BFS

BFS

BFS (Breadth-First Search)는 그래프 탐색 알고리즘으로, 너비 우선으로 탐색하는 방식이다. 시작점에서 가까운 노드부터 탐색하고, 점차 멀리 있는 노드로 나아간다.

---

기본 원리

1. 큐(Queue) 자료구조를 사용: FIFO(선입선출) 방식.
2. 시작점을 큐에 삽입하고 방문 처리한다.
3. 큐에서 노드를 꺼내고, 인접한 미방문 노드를 탐색하며 큐에 추가한다.
4. 더 이상 방문할 노드가 없을 때까지 반복한다.

---

동작 순서

1. 초기화

   • 시작점 방문 처리 (방문 배열 사용).
   • 시작점을 큐에 삽입한다.

2. 반복 탐색

   • 큐에서 노드를 꺼낸다.
   • 꺼낸 노드와 인접한 노드를 확인한다.
   • 미방문 노드는 방문 처리 후 큐에 추가한다.

3. 종료 조건

   • 큐가 비어있으면 탐색이 종료된다.

---

BFS 예시 코드

import Foundation

func bfs(graph: [[Int]], start: Int) {
    var visited = [Bool](repeating: false, count: graph.count)
    var queue = [Int]()
    
    queue.append(start)
    visited[start] = true
    
    while !queue.isEmpty {
        let node = queue.removeFirst()
        print(node, terminator: " ")
        
        for neighbor in graph[node] {
            if !visited[neighbor] {
                queue.append(neighbor)
                visited[neighbor] = true
            }
        }
    }
}

// 예제 그래프 (인접 리스트)
let graph = [
    [1, 3],    // 0번 노드와 연결된 노드
    [0, 2, 4], // 1번 노드
    [1],       // 2번 노드
    [0, 4],    // 3번 노드
    [1, 3]     // 4번 노드
]

// BFS 실행
bfs(graph: graph, start: 0)

실행 결과

0 1 3 2 4

---

그래프 예시

0 - 1 - 2
|   |
3 - 4  

• 인접 리스트 표현:

graph = [
    [1, 3],    # 0번 노드와 연결된 노드
    [0, 2, 4], # 1번 노드
    [1],       # 2번 노드
    [0, 4],    # 3번 노드
    [1, 3]     # 4번 노드
]

시작점 0에서 BFS 실행 결과: 0 -> 1 -> 3 -> 2 -> 4

---

시간 복잡도

• O(V + E): 노드(V)와 간선(E)를 한 번씩 탐색한다.

---

활용 예시

1. 최단 거리 문제: 동일한 비용의 간선에서 최단 경로 탐색.
2. 미로 탐색: 최단 시간에 출구를 찾기.
3. Flood Fill: 그림판 색칠 알고리즘.