잡담.
의무방어전(???)용 문제.. 는 사실 아니고, 리트코드에 데일리로 푸는 챌린지?코딩테스트 연습?이랄 수 있는 문제가 있어서 풀어제낀 문제. 그래프이론을 전공했으면서 코드가 더러워서 싫어하는 유형인 bfs/dfs가 나왔는데 이따가 아래 설명을 보면 알겠지만 상당히 풀이가 더러워서(?) 시간초과 각인 것이 보였다가 결과(Runtime: 639 ms, faster than 94.95% & Memory Usage: 17.3 MB, less than 42.94%)를 보고 엥? 하면서 원래 올릴 생각이었던 것과 다른 이 문제를 올리게 되었다.
문제 설명.
이중 배열로 표현된 행렬이 하나 주어지고, 안에 있는 원소는 모두 0과 1로 이루어져 있다.
그리고 결과는 같은 크기의 행렬로, 각각의 원소에는 원래 행렬에서 가장 가까운 0의 거리가 들어가야 한다.
문제 풀이.
처음 문제를 보았을 때는 어떻게 풀면 좋을지에 대해 고민을 많이 했었다. 결과적으로 코딩 테스트에서 주어진 대상이 메트릭스일때 고질적으로 재일 짜증나게 하는 모서리값에 대한 처리( 3x3 matrix : Mat을 생각해보자. Mat[-1][1]이 인식이 되긴 하지만 3행 2열을 가리키는 원소가 되고, Mat[3][0]은 없는 행렬을 벗어난 값이 때문에 애러가 나게 된다.. + 이건 결과도 메트릭스 꼴이기 때문에 더 별로였다.) 때문에 mat의 값을 그대로 변형시키는 것이 별로 좋지 않아보였고, 결과적으로 로직을 구현할 때 두 가지 과정을 나눠서 코드를 짜게 되었다.
사전에 만들었던 것은
- 행렬의 가로와 새로인
m, n, - derection을 제어하기 쉽게 하기 위한 list인
direction, result라는 return을 시킬, 첫 번째 과정 이전에는 0만 들어가있는 행렬,bfs를 사용하기 위한 Q(deque)
를 정의해주었다.
첫 번째 과정.
첫 번째 과정에서는 0과 맞닿은 1의 값을 가진 행렬의 원소의 위치를 찾아내는 과정이었다. 이 과정에서 코드가 하늘로 뻣어나갈듯이 더러워져서 주어진 행렬의 원소의 위치 i, j(0 <= i < m, 0 <= j < n)에 대해서 주위 네 방향에 0이 있는지를 체크해주는 함수 check를 만들었고, mat[i][j] == 1이면서 check(i,j) == True인 모든 값을 result[i][j]에 들어가는 값인 1과 함께 저장을 해주었다.
두 번째 과정.
본격적으로 bfs를 사용하는 과정.
즉, Q의 원소가 있을 때까지 실행되고, Q가 끝난 시점에서 결과 result가 완성된다. 일반적으로 bfs의 경우 순서에 따라 코드가 반복되게 만들지만, 너무 비효율적이라 생각되어서 FIFO의 속성을 이용해서 저장해주는 값에 result[x][y]에 들어갈 값인 val을 같이 저장해주는 식으로 코드를 돌렸다.
bfs야 어차피 어렵지가 않은(아마도?), 공부를 한 사람이라면 쉽사리 이해가 될 것이기 때문에FIFO와 연관된 코드의 속성에 대해서만 조금 설명을 써놓는다면, 업데이트가 된 것이 아닐 때만 업데이트를 시키는 것과 앞서 뽑힌val1과 뒤에 뽑힌val2를 비교할 때 항상val1 <= val2라는 식이 성립되기 때문이라고만 정리해놓는다.
그리고 Q에 마지막 원소까지 다 소모가 되었으면 결과 result가 완성이 되고, 반환한다.
풀이 코드.
from collections import deque
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m,n = len(mat),len(mat[0])
directions = [(1,0),(0,1),(-1,0),(0,-1)]
def check(i,j):
nonlocal m,n
for k in directions:
x1, y1 = i+k[0], j+k[1]
if x1<0 or y1<0 or x1 == m or y1 == n:
continue
if mat[x1][y1] == 0:
return True
return False
Q = deque()
result = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if mat[i][j] == 1 and check(i,j):
Q.append((i,j,1))
result[i][j] = 1
while Q:
x,y,val = Q.popleft()
for i in directions:
x1,y1 = x+i[0],y+i[1]
if x1<0 or y1<0 or x1 == m or y1 == n:
continue
if (mat[x1][y1] == 1 and result[x1][y1] == 0):
result[x1][y1] = val+1
Q.append((x1,y1,val+1))
return result