Leetcode 542. 01 Matrix

문제. m*n의 행렬이 주어졌을 때, 각셀에서 0이 가장 가까운 거리를 반환하라

 

 

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

01 Matrix - LeetCode

 

 

---

 

처음 접근) 코딩테스트와 프로그래밍 대회에서 만나서 엄청 당황했던 행렬형태의 문제를 다시 만났다....

이번 기회에 확실히 원리를 이해해야겠다! 가장 최단거리를 계산하라 했으므로 BFS임을 직감하고 행과 열을 인덱싱을 통해 호출해야겠다는 생각이 들었지만 해결법이 잘 떠오르지 않았다.

 

 

---

 

다른 사람 답변) 0인 셀을 먼저 처리하는 BFS

class Solution:
	def updateMatrix(self, mat:List[List[int]]) -> List[List[int]]:
    	m, n = len(mat),len(mat[0])
        DIR = [0,1,0,-1,0]
        
        q = deque([])
        
        for r in range(m):
        	for c in range(n):
            	if mat[r][c] == 0:
                	q.append((r,c))
                else:
                	mat[r][c] == -1
                    
        while q:
        	r, c = q.popleft()
            for i in range(4):
            	nr = r + DIR[i]
                nc = c + DIR[i+1]
                if nr <0 or nr ==m  or nc <0 or nc ==n or mat[nr][nc] != -1: continue
               	mat[nr][nc] = mat[r][c] + 1
                q.append((nr,nc))
                    
                #위의 if 문은 0<= nr < m and 0 <= nc <n and (nr,nc) not in q로 대체 가능
        return mat

먼저 앞의 FOR 문에서 이미 0인 값들을 다 Queue에 넣는다. 나머지는 계산이 필요하기 때문에 구별을 위해 -1로 값을 바꾼다. 다음 while 문에서는 q에 있는 값들이 없어질 때까지, 행열번호를 추출하는 r,c를 뽑고 DIR을 활용한 행열 이동을 실행한다.

 

여기서 DIR = [0,1,0,-1,0]은 (0,1) (1,0),(0,-1) (-1,0) 행과열을 오른쪽, 아래쪽, 왼쪽, 위쪽 4가지 방향을 한번에 담아 놓은 리스트이다. 이 때문에 새로운 nr과 nc를 4가지 방향으로 옮겼을 때, 

 

새로운 행열 번호가 음수가 아니고, 각 행열번호가 행번호의 끝, 열번호의 끝을 도달하고, 이동한 행열번호의 값이 0이 아닐때,  즉 작업을 하지 않은 -1인 값에 대해서 1을 더해서 작업을 완료하고  q에 push 를 한다.

 

 

다른 사람 답변) Dynamic programming

class Solution:
	def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    	m, n = len(mat), len(mat[0])
        
        for r in range(m):
        	for c in range(n):
            	if mat[r][c] > 0:
                	top = mat[r-1][c] if r > 0 else math.inf
                    left = mat[r][c-1] if c > 0 else math.inf
                    mat[r][c] = min(top,left) + 1
                    
       for r in range(m-1,-1,-1):
        	for c in range(n-1,-1,-1):
            	if mat[r][c] > 0:
               		bottom = mat[r+1][c] if r < m -1 else math.inf
                    right = mat[r][c+1] if c < n - 1 else math.inf
                    mat[r][c] = min(mat[r][c],bottom + 1, right + 1)
       return mat
                    
                    
                    
#math.inf는 실수형 양의 무한대를 의미함

(티스토리 코드블럭 띄어쓰기가 계속 오류가 나네요....)

 

이 방법은 DP를 이용한 방법으로 4가지 방향으로 가는 위의 방법을 했을 때 이미 계산이 됐는지 모르기 때문에 불필요한 연산을 줄이기 위해 1 ) 좌측상단 셀의 위에서 아래, 왼쪽에서 오른쪽 가는 거리 2) 우측 하단의 셀이 오른쪽에서 왼쪽, 아래에서 위로 가는 거리를 구하는 형식으로 구성했다고 한다.

 

따라서 첫 for-if문에서 top, left를 지정해주고 0이 아닌 셀이 위,아래와 왼오로 갔을 때 최소값, 즉 0이 나오면 기존 왼오에 1이 더해지도록 해서 거리를 기록한다. 아래도 원리는 같다. 다만 range에 (m-1,-1,-1)을 취해주는 이유는 아래 bottom right을 정의할 때 +1 을 해주기 위해서이다.

 

Source: Leetcode hiepit

 

 

 

 

Source:

https://leetcode.com/problems/01-matrix/discuss/1369741/C%2B%2BJavaPython-BFS-DP-solutions-with-Picture-Clean-and-Concise-O(1)-Space 

[C++/Java/Python] BFS, DP solutions - with Picture - Clean & Concise - O(1) Space - LeetCode Discuss