[leetcode] Shortest path binary matrix (BFS)

문제 링크

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

기본적인 BFS문제입니다.

문제 풀이

class Solution {
    func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
        let row = grid.count
        let col = grid[0].count
        var visited = Array(repeating: Array(repeating: false, count: col), count: row)

        var count = -1

        if grid[0][0] != 0 || grid[row-1][col-1] != 0 {
           return count
       }

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

        var queue = [(0,0,1)]
        visited[0][0] = true

        while !queue.isEmpty {
            let cur_x = queue[0].0
            let cur_y = queue[0].1
            let cur_c = queue[0].2

			// 종착점에 도착했으면 count에 현재 단계의 count를 넣고 반복문을 break
            if cur_x == row - 1 && cur_y == col - 1 {
                count = cur_c
                break
            }

            queue.removeFirst()

            for i in 0..<8 {
                let next_x = cur_x + dx[i]
                let next_y = cur_y + dy[i]
                let next_c = cur_c + 1

                if next_x >= 0 && next_y >= 0 && next_x < row && next_y < col && !visited[next_x][next_y] && grid[next_x][next_y] == 0 {
                    visited[next_x][next_y] = true
                    queue.append((next_x, next_y, next_c))
                }
            }
        }
        return count
    }
}

회고

• bfs를 사용하여 넓이 우선 탐색을 진행하며 각 단계마다 count를 세고 종착점에 먼저 도착하는 경우의 count를 return하여 해결하였다.

• 이런 기본적인 문제는 더욱 더 빠르게 떠올리고 작성할 수 있는 연습을 해야할 것 같다.