[백준] BFS - 2178번 미로탐색

2178번: 미로 탐색

 

입력 & 출력

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
(1,1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
각각의 수들은 붙어서 입력으로 주어진다.

 

풀이

BFS 문제로, 탐색 시 최소 이동 값을 저장하여 끝점(N, M)에 도달했을 경우 걸리는 최소 이동 거리를 구한다.

Swift 전체 코드

    let number = readLine()!.split(separator: " ")
    let height = Int(number.first!)!
    let width = Int(number.last!)!
    
    var visited : [[Int]] = .init(repeating: .init(repeating: 0, count: width), count: height)
    var array : [[Int]] = []
    var queue : [(x: Int,y: Int)] = [(0,0)]
    
    let dx = [-1, 0, 1, 0]
    let dy = [0, -1, 0, 1]
   
    visited[0][0] = 1
    
    for _ in 0..<height {
        array.append(readLine()!.map { Int("\($0)")! })
    }
    
    while !queue.isEmpty {
        let point = queue.removeFirst()
        
        for i in 0...3 {
            let x = point.0 + dy[i]
            let y = point.1 + dx[i]
            
            if x < 0 || x >= height || y < 0 || y >= width {
                continue
            }
            
            if array[x][y] == 0 || visited[x][y] > 0 {
                continue
            }
            
            visited[x][y] = visited[point.x][point.y] + 1
            queue.append((x,y))
        }
    }
    
    print(visited[height - 1][width - 1])