DFS DAY2

Max Area of island

DFS 함수를 좀 다르게 구현해봄
recursion을 반복해서 지금 배열요소가 땅이면 1씩 더해서 최댓값 구함

class Solution(object):
    def maxAreaOfIsland(self, grid):
        def DFS(i,j,answer):
            if not grid[i][j]:
                return
            else:
                answer+=1
                grid[i][j]=0                           
            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]==1:
                    answer+=DFS(x,y,0)
            return answer
        max = 0
        for a in range(len(grid)):
            for b in range(len(grid[0])):
                if grid[a][b] == 1 :
                    k = DFS(a,b,0)
                    if max < k : max=k
        
        return max

Number of closed islands

이 문제는 언뜻 보면 floodfill과 같아보이는데 다른 점이 하나 있다
2차원 배열의 외곽이 섬이면 closed된 것이 아니라는 것에 유의해서
먼저 외곽에 섬이 있는 것들을 DFS를 통해 연결된 섬까지도 다 강으로 만들고
그리고 나서 내부에 있는 섬들을 Number of islands문제처럼 풀면 답이 나온다

from collections import deque
class Solution(object):
    def closedIsland(self, grid):
        answer = 0
        q = deque()
        direction=[(0,1),(0,-1),(1,0),(-1,0)]
        def dfs() : 
            while q:
                x,y = q.popleft()
                if 0<=x<len(grid) and 0<=y<len(grid[0]):
                    if grid[x][y]==0:
                        grid[x][y]=1
                        for i in range(4):
                            dx=x+direction[i][0]
                            dy=y+direction[i][1]
                            q.append((dx,dy))
                 
        for i in range(len(grid)):
            if i==0 or i==len(grid)-1:
                for j in range(len(grid[0])):
                    if grid[i][j] == 0:
                        q.append((i,j))
                        dfs()
            else:
                if grid[i][0]==0:
                    q.append((i,0))
                    dfs()
                if grid[i][len(grid[0])-1]==0:
                    q.append((i,len(grid[0])-1))
                    dfs()
        for i in range(len(grid)-1):
            for j in range(len(grid[0])-1):
                if grid[i][j] == 0:
                    answer +=1
                    q.append((i,j))
                    dfs()
        return answer