[Swift] 백준 2178 미로 탐색 (Graph Traversal)

 

📌 풀이

💬 Code

import Foundation

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

var graph = [[Int]]()
var visited = [[Bool]]()

for _ in 0..<n {
    graph.append(readLine()!.map{ Int(String($0))! })
    visited.append(Array<Bool>(repeating: false, count: m))
}

print(bfs(0, 0))

func bfs(_ x: Int, _ y: Int) -> Int {
    var queue = [[Int]]()
    var minLen = 10000

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

    queue.append([x, y, 1])
    visited[x][y] = true

    while !queue.isEmpty {
        let now = queue.removeFirst()
        let len = now[2]

        if now[0] == n - 1 && now[1] == m - 1 { // 도착
            minLen = min(minLen, len)
        }

        for i in 0..<4 {
            let nx = now[0] + dx[i]
            let ny = now[1] + dy[i]

            if 0..<n ~= nx && 0..<m ~= ny && graph[nx][ny] == 1 && !visited[nx][ny] {
                queue.append([nx, ny, len + 1])
                visited[nx][ny] = true
            }
        }
    }

    return minLen
}

 

 

2178번: 미로 탐색