[Leetcode Java] Graphs - Number of Islands

이번에 풀어본 문제는 Number of Island라는 문제로 Graphs 카테고리에 분류되어 있고 난이도는 medium이다.

---

public class NumberOfIslands {
    public static void main(String[] args) {
        char[][] map1 = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        char[][] map2 = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        };
        char[][] map3 = {
            {'1','0','1','0','1'},
            {'0','1','0','1','0'},
            {'1','0','1','0','1'},
            {'0','1','0','1','0'}
        };
        System.out.println("Number of island: " + numIsLands(map1));
        System.out.println("Number of island: " + numIsLands(map2));
        System.out.println("Number of island: " + numIsLands(map3));

    }

    public static int numIsLands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public static void dfs(char[][] grid, int i, int j) {
        if (i < 0 ||
                j < 0 ||
                i >= grid.length ||
                j >= grid[0].length ||
                grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';

        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}

이 코드는 주어진 2차원 배열(grid)에서 "섬"의 개수를 세는 문제를 해결하기 위한 자바 코드이다. 여기서 "섬"이란, '1'로 표시된 연속된 셀을 의미하고, 이 연속된 셀은 상하좌우로만 이동할 수 있다. 섬을 이루는 셀들은 '1'로, 물을 이루는 셀들은 '0'으로 표시된다.

numIslands 함수

1. count 변수를 선언하여 섬의 개수를 저장한다. 초기값은 0이다.
2. 2차원 배열을 순회하면서 각 셀을 검사한다.
   • 만약 셀의 값이 '1'이면, 해당 셀을 시작점으로 하는 섬을 찾기 위해 dfs 함수를 호출한다.
   • dfs 함수 호출 후, count를 1 증가시킨다.

dfs 함수

1. 현재 셀의 위치(i, j)가 배열 범위를 벗어나거나, 값이 '0'인 경우에는 종료한다.
2. 현재 셀을 방문했음을 표시하기 위해 '0'으로 바꾼다.
3. 현재 셀의 상하좌우 셀에 대해 dfs 함수를 재귀적으로 호출한다.

코드가 실행되면서 dfs 함수는 섬에 포함된 모든 셀을 '0'으로 바꾼다. 따라서 그 섬은 다시 카운트되지 않는다. 이런 식으로 모든 셀을 검사하면서 섬의 개수를 셀 수 있다.

이 코드는 Depth-First Search(깊이 우선 탐색) 알고리즘을 사용하고 있다. 이 알고리즘은 공간 복잡도가 (O(M \times N))이고, 시간 복잡도도 (O(M \times N))이다, 여기서 (M)과 (N)은 배열의 행과 열의 개수이다.

---

DFS (깊이 우선 탐색)의 실행 순서를 이해하기 쉽게 설명하기 위해 아래와 같은 2차원 배열을 예시로 들겠다.

[
  ['1', '1', '0', '0'],
  ['1', '1', '0', '0'],
  ['0', '0', '1', '0'],
  ['0', '0', '0', '1']
]

이 배열에서 '1'은 땅을, '0'은 물을 나타낸다. 이 배열에는 총 3개의 섬이 있다.

1. (0,0)에서 시작: 첫 번째 섬

   1. (0,0)을 방문하고 '0'으로 바꾼다.
   2. (1,0)으로 이동하고 '0'으로 바꾼다.
   3. (1,1)으로 이동하고 '0'으로 바꾼다.
   4. (0,1)으로 이동하고 '0'으로 바꾼다.
   5. 더 이상 방문할 곳이 없으므로 이 섬은 완전히 방문 완료.

2. (0,2)에서 시작: 땅이 아니므로 넘어간다.

3. (0,3)에서 시작: 땅이 아니므로 넘어간다.

4. (1,2)에서 시작: 땅이 아니므로 넘어간다.

5. (1,3)에서 시작: 땅이 아니므로 넘어간다.

6. (2,0)에서 시작: 땅이 아니므로 넘어간다.

7. (2,1)에서 시작: 땅이 아니므로 넘어간다.

8. (2,2)에서 시작: 두 번째 섬

   1. (2,2)를 방문하고 '0'으로 바꾼다.
   2. 더 이상 방문할 곳이 없으므로 이 섬은 완전히 방문 완료.

9. (2,3)에서 시작: 땅이 아니므로 넘어간다.

10. (3,0)에서 시작: 땅이 아니므로 넘어간다.

11. (3,1)에서 시작: 땅이 아니므로 넘어간다.

12. (3,2)에서 시작: 땅이 아니므로 넘어간다.

13. (3,3)에서 시작: 세 번째 섬

    1. (3,3)를 방문하고 '0'으로 바꾼다.
    2. 더 이상 방문할 곳이 없으므로 이 섬은 완전히 방문 완료.

총 3개의 섬을 찾았으므로, numIslands 함수는 3을 반환한다. 이런 식으로 DFS 알고리즘은 각 섬을 찾아 나간다.

---

"더 이상 방문할 곳이 없다"는 판단은 dfs 함수 내의 아래 조건문에서 이루어진다.

if (i < 0 ||
    j < 0 ||
    i >= grid.length ||
    j >= grid[0].length ||
    grid[i][j] == '0') {
    return;
}

이 조건문은 다음의 경우에 return 문을 실행해서 현재의 dfs 함수 호출을 종료한다:

1. (i) 또는 (j)가 배열의 경계를 벗어난 경우 (i < 0, j < 0, i >= grid.length, j >= grid[0].length)
2. 현재 위치 ((i, j))가 '0'인 경우, 즉 물인 경우 (grid[i][j] == '0')

이러한 조건들이 모두 만족되지 않을 때만 dfs 함수는 현재 위치의 값을 '0'으로 바꾸고 상하좌우로 계속 탐색한다. 만약 조건 중 하나라도 만족되면, 현재 함수 호출은 종료되고 이전 함수 호출로 돌아가 다른 방향으로의 탐색을 계속한다. 이렇게 해서 "더 이상 방문할 곳이 없다"는 상황을 처리한다.

---

이번 문제를 풀면서 느낀 점은, 상황과 조건에 따라 자유자재로 dfs를 구현할 수 있는 능력을 갖춰야 하겠다는 것이다. 단순히 이런 유형의 문제와 솔루션을 암기한다고 해결되지 않는다. 언제, 어디서, 어떤 유형의 문제가 나와도 응용해서 다 풀어낼 수 있기 위해서는 근본적인 원리에 대해 이해가 되어야하고, 그것을 응용할 수 있도록 충분히 연습해 두어야 하겠다.