<Medium> Number of Islands (LeetCode : C#)

https://leetcode.com/problems/number-of-islands/

📕 문제 설명

1은 land, 0은 water을 나타낼 때 island 개수 반환하기

islad : 땅이 인접해 있으며 물로 둘러싸인 것 (모든 edge가 물로 둘러싸인 것)

• Input
  2차원 행렬 (char[][])
• Output
  island 개수

예제

풀이

기본적인 DFS 문제이다. 땅을 만나면 DFS로 인접한 땅을 모두 visited 처리하고 island 개수를 증가시킨다.

public class Solution {
    public int NumIslands(char[][] grid) {
        int[] dirX = new int[4] {1, -1, 0, 0};
        int[] dirY = new int[4] {0, 0, 1, -1};
        bool[,] visited = new bool[grid.Length, grid[0].Length];
        int numOfIsland = 0;
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[0].Length; j++)
            {
            	// 방문한적 없는 땅이면 island 확인하기 시작
                if (!visited[i, j] && grid[i][j] == '1') 
                {
                    numOfIsland++;
                    DFS(i, j);
                }
            }
        }

        void DFS(int x, int y)
        {
            visited[x, y] = true;

            for (int i = 0; i < 4; i++)
            {
                int currX = x + dirX[i];
                int currY = y + dirY[i];

                if (currX < 0 || currY < 0 || currX >= grid.Length || currY >= grid[0].Length) continue;
                if (!visited[currX, currY] && grid[currX][currY] == '1') DFS(currX, currY);
            }
        }

        return numOfIsland;
        
    }
}

결과