list of list[int] 의 data type을 받아서 가장 긴 connected 1's length를 반환하는 함수를 만들어야 한다.
Matrix 는 2차원이다보니까 m*n Matrix를 생각하면 되고,
주어진 2차원 Matrix에서 어떤 것을 0에서 1로 바꿀 지 잘 고민해야하고
x, y축 index 헷갈리지 않게 주의해야 한다.
이거때문에 index overflow로 애좀 먹음..
꿀팁은
python deque만 있으면 queue / stack 다 구현할 수 있다는 것이고,
python의 경우 if 문에서 0 <= x < 10 이렇게 부등호 두 개를 한 번에 다 쓸 수 있다.
그리고 맨 처음 언급했듯이, x / y축 len과 idx following을 잘 해야 한다.
이런 종류의 문제는 무작정 coding에 들어가지 말고,
머릿속으로 또는 빈 종이에 구조를 잘 구상해놓고 코딩을 시작하자.
그리고 function을 하나 더 또는 두 개 더 만들어 줘야 하는 것은 느낌이 강하게 오는데,
그 함수는 Parameter를 뭘 받을지, output은 어떤 형식으로 반환할 지,
Edge Case는 뭐가 있을 지, 철저히 생각해야 한다.
def problem2(grid: list[list[int]]) -> int:
from collections import deque
m = len(grid[0])
n = len(grid)
def cnt1(grid: list[list[int]]) -> int:
visited = [[False for _ in range(m)] for _ in range(n)]
direction = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
for x in range(n):
for y in range(m):
if grid[x][y]==1 and not visited[x][y]:
q = deque()
cnt = 0
q.append([x,y])
visited[x][y] = True
while q:
curr_x, curr_y = q.pop()
cnt += 1
# visited[curr_x][curr_y] = True
for dy, dx in direction:
new_x = curr_x + dx
new_y = curr_y + dy
# if 0<= new_x <n and 0<=new_y<m and not visited[new_x][new_y] and grid[new_x][new_y]==1 and [new_x,new_y] not in q: # 마지막에 q도 체크해서 중복 cnt 방지하기.. ㅠ
if 0<= new_x <n and 0<=new_y<m and not visited[new_x][new_y] and grid[new_x][new_y]==1 :
q.append([new_x,new_y])
visited[new_x][new_y] = True
ans = max(ans,cnt)
return ans
# test
result = cnt1(grid)
# print("result:",result)
for i in range(n):
for j in range(m):
if grid[i][j] == 0 :
grid[i][j] = 1
temp_cnt = cnt1(grid)
grid[i][j] = 0
result = max(result,temp_cnt)
return result
if __name__ == "__main__":
test = [[1,1],
[0,1]]
print(problem2(test)) #4
test2 = [[1,0,1],
[1,0,1],
[1,0,1]]
print(problem2(test2)) #7
test3 = [[1],
[0],
[1]]
print(problem2(test3)) #3
test4 = [[1,0,1],
[1,0,1],
[1,0,1],
[0,1,0]]
print(problem2(test4)) #8
test5 = [[]]
print(problem2(test5)) #0
test6 = [[0]]
print(problem2(test6)) #1