[Swift] 백준2178 미로탐색

출처 : sun02님 velog

import Foundation

/// 1: 이동가능, 0: 이동불가능
/// (1, 1)에서 (N, M)의 위치로 이동하는 최단거리 구해라
/// dfs 알고리즘 특성 상 최단거리를 찾으려면 완전 탐색을 하고 가장 작은 값을 선택해야 하는데
/// 경로가 아주 많을 수도 있으므로 시간복잡도가 매우 커진다.
/// 그래서 bfs로 풀어야한다.

let NM = readLine()!.components(separatedBy: " ").map { Int($0)! }

let N = NM[0]
let M = NM[1]

let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0]    // 상하좌우

// 0과 1의 정보가 담긴 보드
var board = [[Int]]()

// 방문한 좌표를 담을 배열
var visited = [[Bool]](repeating: [Bool](repeating: false, count: M), count: N)

// 경로를 담을 거리를 담을 배열
var distance = [[Int]](repeating: [Int](repeating: 0, count: M), count: N)

for _ in 0..<N {
    let nums = readLine()!.map { Int(String($0))! }
    board.append(nums)
}

func bfs() {
    distance[0][0] = 1
    visited[0][0] = true
    
    var queue: [[Int]] = [[0, 0]]
    
    while !queue.isEmpty {
        let pop = queue.removeFirst()
        
        let x = pop[0]
        let y = pop[1]
        
        // 좌표를 돌면서 거리 더해주기
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx>=0, nx<N, ny>=0, ny<M {
                if !visited[nx][ny], board[nx][ny] == 1 {
                    distance[nx][ny] = distance[x][y] + 1
                    
                    visited[nx][ny] = true
                    queue.append([nx, ny])
                }
            }
        }
    }
}

bfs()
print(distance[N-1][M-1])