14주차. 그래프(섬의 개수)

32. 섬의 개수

https://leetcode.com/problems/top-k-frequent-elements/

Top K Frequent Elements - LeetCode

📌문제

1을 육지로 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산해라.

 

- 예제1
  📝입력

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

  💻출력

 

Output: 1

📌풀이

5ms, 51.4mb

class Solution {
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public int numIslands(char[][] grid) {
        int answer = 0;
        visited = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == '1' && !visited[i][j]){
                    answer++;
                    dfs(j, i, grid);
                }
            }
        }
        return answer;
    }

    public static void dfs(int x, int y, char[][] map){
        visited[y][x] = true;
        for(int i = 0; i < dx.length; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= map[0].length || ny >= map.length || visited[ny][nx]) continue;
            if(map[ny][nx] == '1'){
                dfs(nx , ny, map);
            }
        }
    }

}