[1스4코2파] # 225 LeetCode 695. Max Area of Island

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (225차)
[4코1파] 2023.01.13~ (217일차)
[1스4코1파] 2023.04.12~ (128일차)
[1스4코2파] 2023.05.03 ~ (106일차)

Today :

2023.08.17 [225일차]
graph
https://leetcode.com/problems/max-area-of-island/

695. Max Area of Island

https://leetcode.com/problems/max-area-of-island/

문제 설명

mXn 의 이진 행렬 grid가 주어질 때, 한 좌표에서 4개의 방향(수직, 수평)은 1로 연결된다면 isalnd가 됨. (0은 물임) 주어진 행렬에서 island 의 총 수를 return

문제 풀이 방법

dfs를 이용해서 푸는데 dfs로 현재 좌표에서 좌,우,위,아래를 recursive하게 조건에 맞을 때까지 돌면서 island 에 해당하는 면적을 return 해줌
아래에서 island의 max값을 return 해줌

내 코드

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        visited = set()
        maxArea = 0

        def dfs(r,c):
            if r<0 or c<0 or r>=rows or c>=cols or grid[r][c]==0 or (r,c) in visited:
                return 0
            visited.add((r,c))
            res = dfs(r-1, c) + dfs(r+1, c) + dfs(r, c-1) + dfs(r, c+1) +1
            return res

        for r in range(rows):
            for c in range(cols):
                if grid[r][c]==1 and (r,c) not in visited:
                    maxArea = max(maxArea, dfs(r,c))
        
        return maxArea      

증빙

여담

이제 좀 dfs가 이해되는 것 같음..
옆에서 그림 그려서 하라는 훈장님 덕분에