백준 - 미로 탐색 (2178)

Seoyoung Lee·2023년 1월 27일
0

알고리즘

목록 보기
24/104
post-thumbnail
struct Queue<T> {
    var input: [T] = []
    var output: [T] = []
    
    var isEmpty: Bool {
        return input.isEmpty && output.isEmpty
    }
    
    var count: Int {
        return input.count + output.count
    }
    
    mutating func enqueue(_ element: T) {
        input.append(element)
    }
    
    mutating func delete() -> T {
        if output.isEmpty {
            output = input.reversed()
            input.removeAll()
        }
        return output.removeLast()
    }
}

let dx = [0, 1, 0, -1]
let dy = [1, 0, -1, 0]

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (N, M) = (input[0], input[1])
var map = [[Int]]()
var visited = Array(repeating: Array(repeating: false, count: M), count: N)
var queue = Queue<[Int]>()

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

bfs(0, 0)

print(map[N-1][M-1])

func bfs(_ x: Int, _ y: Int) {
    visited[x][y] = true
    queue.enqueue([x, y])
    while !queue.isEmpty {
        let now = queue.delete()
        for i in 0..<4 {
            let nowX = now[0] + dx[i]
            let nowY = now[1] + dy[i]
            if nowX >= 0 && nowY >= 0 && nowX < N && nowY < M {
                if map[nowX][nowY] != 0 && !visited[nowX][nowY] {
                    visited[nowX][nowY] = true
                    map[nowX][nowY] = map[now[0]][now[1]] + 1
                    queue.enqueue([nowX, nowY])
                }
                
            }
        }
    }
}
profile
나의 내일은 파래 🐳

0개의 댓글