leetcode(리트코드)-542 01 Matrix(PYTHON)

leetcode 542 - 01 Matrix 문제입니다.

1. 문제

https://leetcode.com/problems/01-matrix/

---

2. Input , Output

---

3. 분류 및 난이도

Medium 난이도 문제입니다.

---

4. 문제 해석

• matrix가 주어집니다.
• 1을 기준으로 가장 가까운 0과의 거리를 찾아 matrix에 저장하고 리턴하세요.

---

5. code

코드설명

• 1을 기준으로 찾으면 시간초과가 뜹니다.
• discuss를 참조하여 0을 기준으로 코드를 작성하니 풀리더군요.

python

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        row = len(mat)
        col = len(mat[0])
        dx = [1,0,-1,0]
        dy = [0,1,0,-1]
        dq = deque()
        for i in range(row):
            for j in range(col):
                if mat[i][j] == 0 :
                    dq.append((i,j))
                else : 
                    mat[i][j] = 987654321
        while dq : 
            x,y = dq.popleft()
            for k in range(4):
                newx,newy = x + dx[k] , y + dy[k]
                z = mat[x][y]+1 
                if 0 <= newx and newx < row and 0 <= newy and newy < col and mat[newx][newy] > z :
                    mat[newx][newy] = z
                    dq.append((newx,newy))
        return mat
    
    
                
                               

---

6. 결과 및 후기, 개선점

필요시 c++로 짜드립니다.

설명이 필요하다면 댓글을 달아주세요.