[자료구조] [python] [BFS/DFS] Connected Cell in a Grid

Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 
www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem?h_r=internal-search

DFS: Connected Cell in a Grid | HackerRank

1) 방문한 점의 값이 1이라면, 방문한 점을 기준으로 거리 1에 해당하는 지점을 리턴하는 함수를 만든다. 단, 한 번이라도 방문하여 체크한 적이 있는지 확인하는 n *m 리스트를 따로 만든다(아래 코드에서 check 리스트에 해당). check리스트에서 한 번이라도 방문한 이력이 있다면 'Y'값을, 한번도 방문하지 않았다면 'N'값을 가진다. 탐색하지 않은 지점만 방문하기 위함이다. 방문한 지점(x,y)을 중심으로 x,y값에 다음의 list의 원소값을 더할 때 itertools의 모듈을 사용하였다. 

 

import itertools

check = [ ["N"]*m for x in range(n)]
list(itertools.product([-1, 0, 1], [-1, 0, 1]))

#list(itertools.product([-1,0,1], repeat=2))로도 표현 가능

 

2) 다음으로, 방문한 점의 값이 1이고, 거리가 1인 주변값들 또한 1일 때, 해당 지점값에서 반복적으로 탐색하는 함수를 만든다. 실제 코드에서는 추가적으로 탐색지점을 늘려가는 방식으로 구현하였다.

#주변체크
def check_adjacent(point, check,n,m):
    candi = list(itertools.product([-1, 0, 1], [-1, 0, 1]))
    tmp = []
    
    for j in candi:
        x, y = point[0]+j[0], point[1]+j[1]

        if 0 <= x < n and 0 <= y < m and check[x][y] =='N':
            if not (x == point[0] and y == point[1]):
                tmp.append([x,y])
    return tmp
        

def maxRegion(grid, n, m):
    #방문여부
    check = [ ["N"]*m for x in range(n)]   
    max_value = 0
    
    for a in range(n):
        for b in range(m):
            point = [a,b]
            
            if grid[point[0]][point[1]] == 1 and check[point[0]][point[1]]=='N':
                temp_value = 1
                temp = check_adjacent(point,check,n,m)
                check[point[0]][point[1]] ='Y'
                #print(point)
                
                while temp:
#                    print(temp)
                    t = temp.pop()
                    if (grid[t[0]][t[1]] == 1) and (check[t[0]][t[1]]=='N'):
                        temp_value+=1
                   #     print(t)
                        check[t[0]][t[1]] = 'Y'
                        temp_add = check_adjacent(t,check,n,m)
                        temp.extend(temp_add)
                
                if max_value < temp_value:
                    max_value = temp_value
                        
                    
            
            elif grid[point[0]][point[1]] == 0:
                check[point[0]][point[1]] = 'Y'
    
    return max_value