스위프트 코딩테스트 강좌, 너비 우선 탐색

1. 서론

너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리 구조에서 노드를 탐색하는 알고리즘입니다.
BFS는 시작 노드에서 인접한 노드들을 먼저 탐색한 뒤 해당 노드의 인접 노드를 탐색하는 방식으로,
모든 수준의 노드를 차례대로 방문합니다. 이 과정은 그래프나 트리를 레벨 단위로 탐색하기 때문에
최단 경로를 찾는 데 유용하며, 많은 문제에서 BFS를 활용할 수 있습니다.

2. 문제 설명

        4 4
        0 0 1 0
        0 1 0 0
        2 0 1 0
        0 0 3 0
        

        7
        

3. 문제 분석

이 문제를 해결하기 위해 BFS를 사용할 수 있습니다.
BFS는 최단 경로를 찾기에 적합한 알고리즘으로, 주어진 격자에서 출발점(2)에서 시작하여
인접한 통행 가능한 영역(0)으로 이동하면서 도착점(3)까지의 경로를 탐색합니다.
이동할 수 있는 방향은 상, 하, 좌, 우 네 가지로 제한됩니다.

BFS의 특징 중 하나는 각 노드를 큐에 추가하기 때문에 레벨 순서대로 탐색하게 됩니다.
따라서 특정 노드에 도달할 때까지의 이동 횟수를 쉽게 카운트할 수 있습니다.
이 방식을 통해 격자를 채운 모든 0과 3을 탐색하면서 도착점에 도달할 수 있는지 확인할 수 있습니다.

4. 알고리즘 설계

1. **격자 및 객체 초기화**: 입력받은 격자를 기반으로 너비 우선 탐색을 위한 큐와 방문 배열을 초기화합니다.
2. **큐에 시작점 추가**: 출발점을 큐에 추가하고 방문 배열을 업데이트합니다.
3. **BFS 수행**: 큐에서 노드를 하나씩 꺼내며, 그 노드의 상하좌우 이웃을 확인합니다.
이웃이 통행 가능한 경우 큐에 추가하고 방문 처리합니다.
4. **도착점 도달 확인**: 도착점에 도달하면 해당 때의 이동 횟수를 출력합니다.
5. **도달 불가능 시 처리**: 큐가 비어도 도착점에 도달하지 못했을 경우 -1을 출력합니다.

5. 코드 구현

이제 위의 알고리즘 설계를 바탕으로 Swift 언어로 BFS를 구현해보겠습니다.

import Foundation

func findShortestPath(grid: [[Int]], start: (Int, Int), end: (Int, Int)) -> Int {
    let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    var queue: [(Int, Int, Int)] = [(start.0, start.1, 0)] // (x, y, distance)
    var visited = grid
    visited[start.0][start.1] = 1 // 방문 처리

    while !queue.isEmpty {
        let (x, y, distance) = queue.removeFirst()
        
        // 도착점에 도달했을 경우
        if (x, y) == end {
            return distance
        }

        // 이웃 노드 탐색
        for direction in directions {
            let newX = x + direction.0
            let newY = y + direction.1
            
            // 유효 범위 내에 있으며 통행 가능한 경우
            if newX >= 0, newY >= 0, newX < grid.count, newY < grid[0].count, visited[newX][newY] == 0 {
                queue.append((newX, newY, distance + 1))
                visited[newX][newY] = 1 // 방문 처리
            }
        }
    }
    
    // 도착점에 도달하지 못한 경우
    return -1
}

// 예시 입력
let grid: [[Int]] = [
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [2, 0, 1, 0],
    [0, 0, 3, 0]
]

if let start = grid.enumerated().flatMap({ $0.element.enumerated().compactMap { $1 == 2 ? ($0.offset, $0.element) : nil } }).first,
   let end = grid.enumerated().flatMap({ $0.element.enumerated().compactMap { $1 == 3 ? ($0.offset, $0.element) : nil } }).first {
    let result = findShortestPath(grid: grid, start: start, end: end)
    print(result) // 최소 이동 횟수 출력
}

6. 코드 설명

위의 코드는 주어진 격자에서 출발점과 도착점을 찾은 후,
너비 우선 탐색을 수행하여 최단 경로를 찾습니다.

• 조사하기 위한 방향은 상, 하, 좌, 우의 4가지 방향을 정의하였습니다.
• 겹치지 않는 노드를 처리하기 위해 visited 배열을 사용하여
  이미 방문한 노드는 더 이상 큐에 추가하지 않도록 하였습니다.
• 도착점에 도달할 시 현재까지의 이동 거리를 반환하게 되어 있습니다.
• 만약 도착점에 도달할 수 없다면 -1을 반환하도록 처리하였습니다.

7. 결론

너비 우선 탐색(BFS)은 최단 경로 탐색 문제를 해결하는 데 매우 유용한 알고리즘입니다.
특히 2차원 격자와 같은 구조에서 효율적으로 동작하며,
여러 프로그래밍 문제에서 빈번하게 등장합니다. 알고리즘의 이해와 문제 해결 능력을 기르기 위해
다양한 유형의 BFS 문제를 연습하는 것이 중요합니다.
이번 강좌를 통해 BFS의 기본 원리를 이해하고 실제 문제를 해결하는 방법을 학습하셨기를 바랍니다.

8. 추가 연습 문제

다음과 같은 변형 문제를 도전해보세요:

• 주어진 격자에서 장애물(1)을 피해 특정 경로만을 이용해 도착점까지 가기.
• 다수의 출발점과 도착점 사이의 최단 경로를 구하는 문제.
• 격자에서 이동하는 대신, 대각선 방향으로도 이동 가능한 경우의 최단 경로 탐색.

이러한 문제들을 통해 너비 우선 탐색 알고리즘에 대한 추가적인 이해와 문제 해결 능력을
더욱 향상시킬 수 있을 것입니다.