[Leetcode - Swift] 1091 Shortest Path in Binary Matrix

문제

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

Shortest Path in Binary Matrix - LeetCode

 

풀이

이 문제는 그래프를 탐색하며 최단 거리를 구하는 문제로 그래프의 대표적인 유형 중 하나다.

나는 처음에 문제 접근을 잘못했다. 매번 노드를 탐색하는 과정을 dfs 재귀로 구현하려고 했다. (저번 문제에서 재귀를 배웠더니 이를 연습하려는 마음에 문제를 잘못 해석했던 것 같다.)

 

하지만, 이 문제는 최단 거리를 찾는 문제이므로 bfs를 통해 각 level을 일괄적으로 탐색해야 했다.

이렇게 bfs로 구현했음에도 불구하고 시간 초과가 떴는데, 그 이유는 큐에 방문할 노드를 추가하는 과정에서 (queue.append) 인접한 노드에 해당하면 모든 노드가 추가되었다. 즉, 중복이 모두 허용된 상태로 큐에 추가되다보니, 시간 초과가 발생할 수 밖에 없었다. 이를 피하기 위해 큐에 인접 노드를 추가하면서 곧바로 방문했다는 처리를 해주었더니, 그다음 노드부터 중복된 노드가 추가되지 않았다. (이를 알고 뒤늦게 다른 풀이들을 보니 다 중복 처리를 해주었다.)

 

처음 문제를 해석할 때는 쉽다고 판단했으나, 2hr 15min이나 걸렸다... 집중력도 문제 해결력도 최악 of 최악이었으나, 끝까지 풀어낸 것에 집중해서 긍정적으로 생각하자. 다음부터는 더 집중해서 문제를 풀어내자.

 

코드

import Foundation

class Solution {
    func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
        guard grid.count > 1 else { return grid[0][0] == 0 ? 1 : -1 }
        guard grid[0][0] == 0 && grid.last!.last! == 0 else { return -1 }
    
        return bfs(grid)
    }

    fileprivate func bfs(_ grid: [[Int]]) -> Int {
        var count = 0, mGrid = grid, queue = [(0,0)]
        let n = grid.count, dx = [-1,-1,0,1,1,1,0,-1], dy = [0,1,1,1,0,-1,-1,-1]

        while !queue.isEmpty {
            count += 1
            for _ in 0..<queue.count {
                let current = queue.removeFirst()
                
                if current.0 == (n-1) && current.1 == (n-1) {
                    return count
                }
                
                for i in 0..<8 {
                    let newX = current.0 + dx[i], newY = current.1 + dy[i]
                    if newX < n && newX >= 0 && newY < n && newY >= 0 && mGrid[newX][newY] == 0 {
                        queue.append((newX,newY))
                        mGrid[newX][newY] = 1
                    }
                }
            }
        }
        
        return -1
    }
}