[DFS] leetcode 695번 Max Area of Island

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

Max Area of Island - LeetCode

 

# 문제

# 예시

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
               [0,0,0,0,0,0,0,1,1,1,0,0,0],
               [0,1,1,0,1,0,0,0,0,0,0,0,0],
               [0,1,0,0,1,1,0,0,1,0,1,0,0],
               [0,1,0,0,1,1,0,0,1,1,1,0,0],
               [0,0,0,0,0,0,0,0,0,0,1,0,0],
               [0,0,0,0,0,0,0,1,1,1,0,0,0],
               [0,0,0,0,0,0,0,1,1,0,0,0,0]]

Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

 

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

# Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

 

# 해석

처음에 최적화의 집중하다 보니 틀린 풀이에 접근하였다.

이 풀이를 통해서 다음 DFS문제를 풀 때, 더 빠르고 좋은 해답을 적기 위해 글을 적는다.

 

(1) 2중 for문으로 직사각형을 훑으며 내려가며 검사하는 방법을 생각했다.

이때, 처음 생각한 방법은 

이전에 포스팅했던 

https://codewizard.tistory.com/29

[stack] 백준 24463번, 미로

영상처리 알고리즘을 이용한 풀이를 생각했다.

case를 4개로 검사하는 거다.

나는 이방식으로 풀 수 있었지만, 정확한 시간복잡도를 미리 생각해보지 않았고 

이 방식으로 보통 풀라고 낸 출제자의 의도가 아님을 알았다.

미리 시간복잡도적으로 생각을 해보았다면 썼을 수도 있다고 생각한다.

왜냐하면 "코딩테스트를 준비"를 위해서 문제를 풀고 있었기 때문에 시간 안에 빠른 정답도출이 문제였다.

 

그래서 DFS로 접근하였다.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:  
        len_col = len(grid[0]) # 열
        len_row = len(grid) # 행 

        # 결과 보기
        # for i in range(len(grid)):
        #     print(grid[i])
        max_area = 0
        for i in range(len_row): # 행만큼 반복
            for j in range(len_col): # 열만큼 반복
                if grid[i][j] == 1: # 새로운 섬이라면 
                    area = self.dfs(grid, i, j)
                    max_area = max(area, max_area)
        
        print("max:", max_area)
        return max_area
        
    def dfs(self, grid, y, x):
        
        # 상하좌우 검색, 상좌는 이미 갔다옴 
        area = 1
        grid[y][x] = 0 # 방문섬 표시

        # 하
        # if y+1 < len(grid): # 더 작을때만 
        #     if grid[y+1][x] == 1: # 같은 섬이라면

        if y + 1 < len(grid) and grid[y + 1][x] == 1:
            area += self.dfs(grid, y+1, x)        
                
        # 우
        if x + 1 < len(grid[0]) and grid[y][x + 1] == 1:
        # if x+1 < len(grid[0]): # 더 작을때만
        #     if grid[y][x+1] == 1:
            area += self.dfs(grid, y, x+1)   

        return area

처음 접근한 코드다.

이 방법을 이용하여 예제 1번을 입력하면 

정답이 5가 나온다.

사진에 주황색이 가장커서 6이나오는데

나는 for문이 우, 하 방향으로 나아가는 것에 집중하다 보니

보라색에서 1,2번으로 가게 짰더니 위로 가지 않아서 1개가 무시되어 

답이 5가 나왔다.

 

sol: 따라서 이 코드를 통해서 얻은 것은 인접 DFS를 검사할 때, 인접한 것을 모두 검사하되 

      idx값이 밖으로 나가는지 안 나가는지만 파악한다.

 

# 솔루션 코드

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:  
        len_col = len(grid[0]) # 열
        len_row = len(grid) # 행 

        # 결과 보기
        # for i in range(len(grid)):
        #     print(grid[i])
        max_area = 0
        for i in range(len_row): # 행만큼 반복
            for j in range(len_col): # 열만큼 반복
                if grid[i][j] == 1: # 새로운 섬이라면 
                    area = self.dfs(grid, i, j)
                    max_area = max(area, max_area)
        
        print("max:", max_area)
        return max_area

    def dfs(self, grid, y, x):
        
        # 하나라도 만족하면 갈 수 없음.
        # 아래 상하좌우에서 그냥 무조건 반복하고
        # 반복했을 때 조건에 어긋나면 섬을 나간거임
        if x<0 or y<0 or x+1>len(grid[0]) or y+1>len(grid) or grid[y][x] != 1:
            return 0

        # 유효하다면 그때 방문가능섬 표시
        area = 1
        grid[y][x] = 0 # 방문섬 표시

        # 상하좌우
        area += self.dfs(grid, y-1, x)  # 상
        area += self.dfs(grid, y+1, x)  # 하
        area += self.dfs(grid, y, x-1)  # 좌   
        area += self.dfs(grid, y, x+1)  # 우 

        return area

이것이 좋은 코드인 것 같다.

if문에서 

1) idx 값이 나가는지 안 나가는지 4개의 확인

2) 마지막 or == 1이 아닌지 맞는지 검사한다.

 

정도의 과정을 통해서 dfs를 부를 수 있다.

 

# 얻은 점

• 방문 지점을 그냥 0으로 처리한다. (최적화) => 나는 인접행렬에 저장하고 다시 확인하는 작업을 거치려 했다.
• 그러지 않고 바로바로 max를 통해서 제일 큰 값을 비교하면 된다.