1과 0으로 이루어진 list가 있다. 상하좌우로 연결된 1은 하나의 땅을 의미한다.
주어진 리스트에서 땅의 개수를 구하라.

24-06-28 (Time Over.)

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, 등..