[LeetCode] 542. 01 Matrix (파이썬)

542. 01 Matrix - 파이썬 풀이

< 목차 >

1. 문제접근 아이디어
2. 구현코드

문제접근 아이디어

• 해당 문제는 백준에 7569번 토마토라는 문제가 존재하는데 이 문제와 매우 흡사하다. 거의 똑같다. (클릭 시 해당 문제로 이동)
• 가장 이 문제는 1에서 가장 가까운 0까지의 거리를 적는 문제이다. 그럼 0에서 1까지의 거리를 써주면 된다.
• 근데 최소거리를 써줘야 하는 문제이기 때문에 값이 0인 인덱스를 전부 Queue에 넣고 빼면서 bfs를 해주면 가장 가까운 0이 제일 먼저 해당 1에 도달을 할 것이다.
• 그래서 distance값이 초기 설정과 달라지면 최소 거리를 찾은 것이다.
• bfs를 하는 방법은 인접 인덱스가 인덱스 범위 안에 있거나 방문한 적이 없다면 즉, distance가 초기 값과 같다면 Queue에 넣어주고 Queue가 빌 때까지 이를 반복한다.

구현코드

from collections import deque
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        def bfs(mat, visited, q):
            while q:
                x, y= q.popleft()
                for d in range(4):
                    nx, ny = x + dx[d], y + dy[d]
                    if 0<=nx<len(mat) and 0<=ny<len(mat[x]) and visited[nx][ny] == -1:
                        q.append((nx, ny))
                        visited[nx][ny] = visited[x][y]+1

        q = deque()
        dx = (0, 1, 0, -1)
        dy = (1, 0, -1, 0)
        visited = [[-1]*len(mat[i]) for i in range(len(mat))]
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                if mat[i][j] == 0:
                    q.append((i, j))
                    visited[i][j] = 0
        bfs(mat, visited, q)
        return visited