LeetCode 695(Max Area of Island, java)

0. 문제

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

Max Area of Island - LeetCode

 

 

1. 문제 설명

- 문제에서 이중 배열(= grid)이 주어진다.

- 이중 배열의 값으로 1과 0이 주어지는데, 0은 바다를 의미하고 1은 땅을 의미한다.

- 상하좌우로 연결된 1의 값을 계산하여, 그중 가장 큰 값(= 가장 큰 땅)을 반환하는 것이 문제의 핵심이다.  

- 이 문제는 재귀 함수에 대한 기본적인 이해가 있다면 충분히 풀 수 있는 문제다.

 

 

2. 문제 해설

a) 첫 번째 접근

- 이전 포스팅에서 풀었던 문제와 매우 유사한 형태의 문제다.

- 어떤 요소의 상하좌우에 위치한 요소의 값이 1인 경우, 해당 요소의 상하좌우를 계속해서 검사한다.

- 요소의 값이 0이거나 이미 검사한 요소라서 더 이상 검사할 요소가 존재하지 않는 경우 멈춘다.

 

- 즉, 재귀 함수를 이용하여 이를 구현다. 

 

 

b) 두 번째 접근

- 요소를 탐색할 때 가장 중요한 것은 이미 검사한 요소를 중복 검사하지 않는 것이다.

- 자료구조를 따로 만들어 방문한 요소의 위치를 기록할 수 있다.

- 그러나 가장 쉬운 방법은 방문한 요소의 값을 0으로 만드는 것이다.

- 요소의 값이 0인 경우, 검사할 이유가 없기 때문이다.

 

 

c) 세 번째 접근

- 문제에서 이중 배열이 주어지지만, 시작 위치는 주어지지 않는다.

- 그러므로 모든 요소를 다 탐색하면서 요소의 값이 1인 위치를 찾아야 한다. 

- 이중 배열의 모든 요소를 다 탐색해야 하므로, 이중 for문을 구사하면 되겠다.

 

- 다음 코드를 보면서 이해해보자. 

 

 

3. 정답 코드

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        
        int maxArea = 0;
        int row = grid.length;
        int col = grid[0].length;
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                maxArea = Math.max(maxArea, findArea(grid, i, j));
            }
        }
        return maxArea;
    }
    
    public int findArea(int[][] grid, int r, int c) {
        if(r < 0 || c < 0 || r >= grid.length 
           || c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }
        
        grid[r][c] = 0;
        
        return (1 + findArea(grid, r - 1, c) 
                + findArea(grid, r + 1, c) 
                + findArea(grid, r, c - 1) 
                + findArea(grid, r, c + 1));
    }
}