Daily LeetCode Challenge - 1162. As Far from Land as Possible

Problem From.

https://leetcode.com/problems/as-far-from-land-as-possible/

오늘 문제는 2차원 배열이 주어질때, 0으로 되어있는 각각의 칸에서 1까지의 거리가 최단거리로 계산했을때 가장 먼 길이를 찾는 문제였다.

최단 거리로 계산했을때 가장 먼 길이를 찾는 부분이라 조금 헷갈렸는데,
BFS 를 기반으로 풀면서 queue 가 빌때까지 전부 검사하는게 아닌, queue 의 길이를 한번 검사를 시작할때 한정지어놓고, 그만큼만 돌리면 되는 문제였다.

class Solution {
    
    val direction = arrayOf(Pair(-1, 0), Pair(0, -1), Pair(1, 0), Pair(0, 1))
    
    fun maxDistance(grid: Array<IntArray>): Int {
        
        val size = grid.size
        
        val visited = Array(size){IntArray(size) { 0 }}
        val queue : Queue<Pair<Int,Int>> = LinkedList()
        for(i in 0 until size) {
            for(j in 0 until size) {
                visited[i][j] = grid[i][j]
                if(grid[i][j] == 1){
                    queue.add(Pair(i,j))
                }
                
            }
        }
        
        var distance = -1
        while(queue.isNotEmpty()) {
            var size = queue.size
            while(size-- > 0) {
                val temp = queue.poll()
                direction.forEach {
                    val x = temp.first + it.first
                    val y = temp.second + it.second
                    if(x >= 0 && y >= 0 && x < grid.size && y < grid.size && visited[x][y] == 0) {
                        visited[x][y] = 1
                        queue.add(Pair(x, y))
                    }
                }
            }
            distance += 1
        }
        return if(distance == 0) -1 else distance
    }

}

위 문제의 시간복잡도는 O(M * N) 이 된다.