-
[자료구조] [python] [BFS/DFS] Connected Cell in a GridData miner/Algorithm & Data structure 2021. 2. 24. 17:30728x90
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자.
www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem?h_r=internal-search1) 방문한 점의 값이 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
'Data miner > Algorithm & Data structure' 카테고리의 다른 글
[정렬] 기수 정렬 알고리즘 (0) 2021.03.21 [자료구조] [python] [BFS/DFS] Shortest Reach in a Graph (0) 2021.02.25 [자료구조] [python] [heapq] Minimum Average Waiting Time (0) 2021.02.17 [자료구조] [heapq] Jesse and Cookies (0) 2021.02.09 [자료구조] [python] [heapq] QHEAP1 (0) 2021.02.09