[HR] Search : Connected Cells in a Grid

문제요약

• 0과 1로 이루어진 매트릭스에서 1로 연결된 가장 큰 그룹의 크기 찾기

아이디어

DFS 알고리즘을 공부했다면 바로 DFS를 떠올릴 수 있다.
상하좌우 뿐만 아니라 대각선도 연결된 것으로 보기 때문에 8가지 액션을 취하는 것을 고려한다.
한 번 방문한 cell은 10을 곱해서 방문처리해준다.

코드(성공)

def dfs(x, y, cnt, moves):
    if 0 <= x < n and 0 <= y < m and matrix[x][y] == 1:
            
        cnt += 1
        matrix[x][y] = cnt * 10
        
        for mv in moves:
            n_x = x + mv[0]
            n_y = y + mv[1]
            cnt = dfs(n_x, n_y, cnt, moves)
            print(cnt)
        # dfs(x+1, y, cnt, moves)
        # dfs(x-1, y, cnt, moves)
        # dfs(x, y+1, cnt, moves)
        # dfs(x, y-1, cnt, moves)
        
    return cnt
    

def connectedCell(matrix):
    # Write your code here
    mx= 0
    moves = [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (1, 1), (-1, 1), (1, -1)]
    moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                cnt = 0
                print(i, j)
                result=dfs(i,j, cnt, moves)
                # print(result)
                mx = max(mx, result)
    return mx