1과 0으로 이루어진 list가 있다. 상하좌우로 연결된 1은 하나의 땅을 의미한다.
주어진 리스트에서 땅의 개수를 구하라.
from collections import deque
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
self.grid = grid
self.m = len(grid)
self.n = len(grid[0])
idxland = self.indexislands()
searching_space = len(idxland)
islands = 0
discovered = []
if searching_space > 0:
while len(idxland) > 0:
v = idxland.popleft()
if not v in discovered:
islands +=1
discovered = self.DFS(v, discovered)
return islands
else:
return islands
def DFS(self, v, discovered = []):
if not v in discovered:
discovered.append(v)
vx, vy = v
adjacent = [(vx-1, vy), (vx, vy-1), (vx+1, vy), (vx, vy+1)]
for adj in adjacent:
if not adj in discovered:
adjx, adjy = adj
if adjx < self.m and adjy < self.n and adjx >= 0 and adjy >= 0:
if self.grid[adjx][adjy] == "1":
self.DFS(adj,discovered)
return discovered
def indexislands(self):
indislands = deque([])
for m in range(self.m):
for n in range(self.n):
if self.grid[m][n] == "1":
indislands.append((m,n))
return indislands
DFS을 이용해서 "연결된 땅"을 정의하고자 했다.
1. 그래프 최상단 노드 구하기 : 주어진 리스트에서 1로 적힌 값의 index를 구함.
2. 그래프 최상단 노드에서 각각 DFS 진행
DFS 진행 시 좌우상하 4가지 노드를 연결노드로 진행.
결과는 Time over..
1번의 과정을 생략하면 통과할 수 있을 것 같다.
주어진 리스트에서 1로 적힌 노드부터 DFS를 진행하여 마지막 m-1, n-1 값까지 searching 하는 것이다.
나의 코드에서는 discovered 라는 리스트로 탐색 구역을 저장했는데, "1" -> "0"으로 변경하면서 탐색 구역을 체크하는 것이 좋을 것 같다 (저장 공간 절약)
Tip. 네 방향 각각 DFS 재귀를 사용하자. (파이썬 알고리즘 책 p.332)
-> 왼쪽으로 탐색하는 DFS, 오른쪽으로 탐색하는 DFS, 등..