백준 2178번 미로 탐색

 정답 :

let num = readLine()!.split(separator: " ").map { Int($0)! }

let row = num[0]
let col = num[1]
var array: [[Int]] = []
var visited = Array(repeating: Array(repeating: false, count: col), count: row)
var queue: [(Int, Int)] = []
var count = 0

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

func bfs(array: [[Int]]) {
    let dr = [0, 1, 0, -1]
    let dc = [1, 0, -1, 0]
    
    queue.append((0, 0))
    visited[0][0] = true
    
    while !queue.isEmpty {
        let queueSize = queue.count
        
        for _ in 0..<queueSize {
            let (cur_r, cur_c) = queue.removeFirst()
            
            if cur_r == row - 1 && cur_c == col - 1 {
                print(count + 1)
                return
            }
            
            for i in 0..<4 {
                let next_r = cur_r + dr[i]
                let next_c = cur_c + dc[i]
                
                if 0 <= next_r && next_r < row && 0 <= next_c && next_c < col {
                    if !visited[next_r][next_c] && array[next_r][next_c] == 1 {
                        queue.append((next_r, next_c))
                        visited[next_r][next_c] = true
                    }
                }
            }
        }
        
        count += 1
    }
    
    print(-1)
}

bfs(array: array)

 

직전 문제인 그림 문제와 가장 큰 차이점은 최단 경로가 있다는 점이다.

 

해당 코드는 최단 경로를 구하기 위해 queueSize 변수를 이용하여 풀었다.

 

queueSize 변수를 사용한 이유는 현재 큐에 있는 원소만 처리하고, 같은 레벨에 있는 원소들을 처리한 후에야 다음 레벨의 원소를 처리해야 하기 때문이다.