[Swift] BFS 예제와 풀이 (백준 2178 미로 탐색)

[Swift] BFS 예제와 풀이 (미로 탐색)

BFS (Breadth First Search, 너비 우선 탐색)

• 인접한 노드들을 우선 탐색하는 방식.
• 가까운 노드부터 탐색하는 알고리즘.
  • 1950년 미로를 탈출하는 가장 짧은 경로를 찾기 위해 탄생한 알고리즘이다.
• 큐를 사용해 구현하는 것이 정석이다.
  • 인접 노드를 큐에 넣으면 자연스럽게 선입선출이 되어 가까운 노드부터 탐색하게 된다.
• O(n) 의 시간복잡도를 가진다. (n = 데이터의 개수)
• 일반적인 경우 실제 수행 시간은 DFS보다 BFS가 빠른 편이다.

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.
2. 큐에서 노드를 꺼내, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
   1. 만약 인접 노드 중 방문하지 않은 노드가 여러 개면, 값이 낮은 노드 or 왼쪽 노드를 먼저 큐에 삽입한다.
3. 정답을 찾거나, 모든 노드를 탐색할 때까지 2.를 반복한다.
   1. 정답을 찾았다면 탐색을 멈춘다.

---

예제 - 백준 2178 미로 탐색

2178번: 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

예제1에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

---

풀이

let inputArr = readLine()!.split(separator: " ").map { Int($0)! }
let n = inputArr[0]
let m = inputArr[1]

var maze = [[Int]]()

for _ in (0..<n) { // 미로를 이차원배열에 입력
    let innerArr = readLine()!.map { Int(String($0))! }
    maze.append(innerArr)
}

var queue = [(0,0)] // 큐에 미로의 시작점을 넣고 시작

let dx = [-1, 1, 0, 0] // 상하좌우 1칸씩 이동할 떄의 x좌표, y좌표
let dy = [0, 0, -1, 1]

while !queue.isEmpty { // 큐가 빌 때까지 반복
    let (x, y) = queue.removeFirst()

    for i in (0..<4) { // xy의 상하좌우에 대해
        let nx = x + dx[i] // x좌표, y좌표 이동
        let ny = y + dy[i]

                // x 또는 y 좌표가 미로를 벗어나면 이동x
        if nx < 0 || ny < 0 || nx >= n || ny >= m {
            continue
        }
                // xy 좌표 이동 시 벽(0)을 만나면 이동x
        if maze[nx][ny] == 0 {
            continue
        }
                // xy 좌표 이동 후 통로(1)를 만나면 이동
        if maze[nx][ny] == 1 {
            maze[nx][ny] = maze[x][y] + 1
            queue.append((nx, ny))
        }
    }
}
print(maze[n-1][m-1])

위와 같이 풀면 방문 처리를 할 때마다 이동 전 위치의 값+1을 이동 후 위치의 값으로 할당하기 때문에, 미로의 좌표 값은 모든 시행이 끝나고 아래와 같은 모습이 된다.

따라서 맨 오른쪽 아래(출구) 에 도달했을 때의 값을 출력하면 이동한 칸수가 된다(15).

[0, 0, 0, 0, 0], // 이동 전
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
⬇️
[3, 0, 9, 10, 11, 12], // 이동 후
[2, 0, 8, 0, 12, 0], 
[3, 0, 7, 0, 13, 14], 
[4, 5, 6, 0, 14, 15]

BFS의 핵심은 큐에 작업목록을 넣고, 큐가 빌 때까지 현재 위치의 주변을 탐색하는 것인 것 같다.

스택을 DFS와 달리 큐를 쓰기 때문에, 큐에 입력된 순서대로 이동이 처리된다.