알고리즘 공부 Leetcode Day8

오늘은 그동안 배웠던 Binary Search, Two Pointer 알고리즘 방식이 아닌 DFS(깊이 우선 탐색) 알고리즘 문제를 풀 예정이다.

 

문제를 풀기 앞서 먼저 DFS 알고리즘이 뭔지 알고 가야 한다.

 

밑에 있는 그림 자료를 인용하여 필자가 이해한 내용을 풀어쓰려고 한다.

 

1. 맨 처음 단계에서는 첫 시작 정점을 기준으로 만약 0번째로 잡고 시작하였을 때 0번째 정점을 방문한다.

 

2. 그 후 0번째 정점과 인접한 정점 중에서 작은 수를 방문한다.

3. 그다음 동일한 방식으로 1 정점에서 방문하지 않은 정점 중 작은 수를 방문한다.(2 정점)

 

4. 이렇게 방문하지 않은 정점, 작은 수 정점을 방문하는 방식으로 모든 정점을 방문한다

 

5. 모든 정점을 방문하고 더 이상 방문할 정점이 없다면 DFS를 종료한다.

 

따라서 이 그림에서는 0->1->2->3->4->6->5 방식으로 방문을 하였다.

 

이런 개념을 전제로 문제를 풀 예정이다.

 

오늘 풀어볼 문제는 

 

695. Max Area of Island

Medium

8089179Add to ListShare

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

 

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.

이 문제는 1이 붙어있는 것이 섬으로 판단하고 그중 가장 많이 붙어있은 섬의 크기를 출력해야 한다.

이 문제를 보았을 때 우선 2차원 배열의 값이 이미 주어지므로 각각 for문을 통해 grid 위치가 1인 것에 대한 위치를 재귀 함수로 풀어볼 생각이다.

 

만약 grid 위치가 1일 경우 그 자리를 0으로 바꾼 다음 위, 아래, 왼쪽, 오른쪽에 대한 재귀를 돌리고 

조건문을 통해 배열 크기보다 넘거나 적으면 리턴 0을 시키면 해결할 수 있다 판단되었다.

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int result = 0;
        int row = grid.length; //testcase 8
        int column = grid[0].length;//testcase 13
        for (int i = 0; i < row; i++){
            for (int j = 0; j < column; j++){
                if (grid[i][j] > 0) {
                    result = Math.max(result, dfs(i, j, grid));
                }
           }
        }
        return result;
    }
    public int dfs(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] < 1) {
            return 0;
        }
        grid[i][j] = 0;
        return 1 + dfs(i-1, j, grid) + dfs(i, j-1, grid) + dfs(i+1, j, grid) + dfs(i, j+1, grid);
        //행,열 이아래 
    }
}

위와 같이 코드를 보자면 grid 2차원 배열을 받고 행, 열 크기를 변수로 넣었다.

그 뒤 행 크기, 열 크기만큼 반복문을 돌리되 grid [i][j]의 위치에 값이 0보다 크면(1일 경우)

result 배열에다가 섬의 크기를 구하는 재귀 함수를 계산한다

 

밑에 dfs 클래스에서는 현재 행, 열 위치,grid 배열 을 받고

먼저 현재 행,열 위치가 배열의 크기 안에 있는 조건을 걸고 재귀하면서 0이 되면 리턴할 수 있게 grid [i][j]<1을 통해 구현하였다.

 

조건에서 False 가 뜨는 것은 붙어있는 1일 것이고 그 위치를 0으로 만들고 return에서 다시 한번 위, 아래, 왼쪽, 오른쪽 재귀를 돌린다 이때 +1을 하여 섬의 크기를 이어 붙인다.

 

이 문제는 DFS알고리즘 문제를 풀다 보면 꼭 나오는 문제이다.

그만큼 이 문제를 통해 풀었다는 것은 DFS 개념을 이해했다는 것이다.

필자는 Java로 풀기 전에 이미 DFS를 예전에 Python으로 시도한 적이 있었기에 이 알고리즘 접근은 크게 어렵지 않았다. 하지만 오랜만에 푸는 만큼 헷갈리는 문제였고 이 문제를 토대로 다음에도 직접 다시 풀면서 완전히 내 것으로 이해하는데 노력해야 할 것이다.

 

 

 

 

 

알고리즘 설명 그림 참고 사이트 : https://miiinnn23.tistory.com/m/14