[HackerRank] Connected Cells in a Grid

def bfs(x,y,area,row,column,visited):
    
    if area[x][y] != 1 or visited[x][y]:
        return 0
    
    count = 1
    visited[x][y] = True
    
    queue = [(x,y)]
     
    nx = [-1,1,0,0,-1,-1,1,1]
    ny = [0,0,-1,1,-1,1,-1,1]
    
    while queue:
        v = queue.pop(0)
        
        for i in range(8):
            temp_x = v[0] + nx[i]
            temp_y = v[1] + ny[i]
            
            if temp_x >= 0 and temp_x < row and temp_y >= 0 and temp_y < column:
                if area[temp_x][temp_y] == 1 and not visited[temp_x][temp_y]:
                    queue.append((temp_x,temp_y))
                    visited[temp_x][temp_y] = True
                    count += 1
                    
    return count
            
def connectedCell(matrix):
    # Write your code here
    
    row = len(matrix)
    column = len(matrix[0])
    
    visited = [[False]*column for _ in range(row)]
    
    max_value = 0
    
    for i in range(row):
        for j in range(column):
            value = bfs(i,j,matrix, row, column, visited)
            if value > max_value:
                max_value = value
                
    return max_value

이번 문제는 0과 1로 이루어진 2차원 리스트가 주어졌을 때, 상-하-좌-우와 대각선 기준으로 인접한 영역이 가장 큰 영역의 크기를 구하는 문제이다.

 

이전에 백준에서 풀이했었던 문제와 많이 상이하여 금방 풀이할 수 있었는데, 다만 함수에서 또 다른 함수를 부르는 방식이라 DFS를 사용할지 BFS를 사용할지 고민하다가 결국 BFS 알고리즘을 사용하여 풀이하였다.