[LeetCode] BFS 와 접근법

[LeetCode] BFS 와 접근법

문제: 542. 01 Matrix

풀이: BFS 로 정답을 유추해야한다.
처음에 시간초과가 났었는데 그 이유는 0 이 아닌 모든 노드들을 기준으로 bfs 를 돌렸기 때문이다.
이렇게 되면 visited 배열을 1번 bfs 돌릴때마다 일일이 초기화 해야하는 비효율성이 있었고, 이미 탐색한 노드를 여러번 봐야한다.
물론 위의 풀이도 맞는 풀이긴 한데 비효율적이고 시간이 오래걸림

하지만, 0인 노드를 기준으로 bfs 를 돌리면, queue 특성상, dx,dy 로 move 한 노드의 값은 현재 노드의 값 + 1 이 된다. 따라서 이 특징을 활용하면 visited 배열을 딱 1번만 만들면 되고, 이미 방문했던 노드는 다시 방문할 필요가 없다는 장점이 있다.

from collections import deque

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:

        n = len(mat)
        m = len(mat[0])

        visited =  [[0] * m  for _ in range(n)]

        queue = deque()

        for i in range(n):
            for k in range(m):
                if (mat[i][k] == 0):
                    queue.append([i,k])
                    visited[i][k] = 1

        def bfs():
            nonlocal queue, mat

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

            while (queue):
                [curY, curX] = queue.popleft()
                for i in range(4):
                    newY = curY + dy[i]
                    newX = curX + dx[i]

                    if (0 <= newY < n and 0 <= newX < m and not visited[newY][newX]):
                        mat[newY][newX] = mat[curY][curX] + 1
                        visited[newY][newX] = 1
                        queue.append([newY,newX])
        bfs()
        return mat

994. Rotting Oranges

BFS 를 활용한 풀이

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:

        n = len(grid)
        m = len(grid[0])

        visited = [[0] * m for _ in range(n)]

        queue = deque()
        freshOrange = 0
        r = 0

        for i in range(n):
            for k in range(m):
                if (grid[i][k] == 2):
                    queue.append([i,k,0])
                    visited[i][k] = 1
                elif (grid[i][k] == 1):
                    freshOrange += 1
                else:
                    visited[i][k] = 1

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

        while (queue):    
            [curY, curX, cnt] = queue.popleft()
            r = cnt

            for i in range(4):
                newY = curY + dy[i]
                newX = curX + dx[i]
                if (0 <= newY < n and 0 <= newX < m and not visited[newY][newX]):
                    visited[newY][newX] = 1
                    freshOrange -= 1
                    queue.append([newY,newX,cnt+1])
        if freshOrange == 0:
            return r
        else:
            return -1