15주차. 그래프(섬의 개수 리팩토링)

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

📌풀이

3ms, 51.1mb

public class Solution {

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

    public void dfs(char[][] map, int y, int x){
        if(x < 0 || y < 0 || x >= map[0].length || y >= map.length || map[y][x] == '0') return;
        map[y][x] = '0';
        dfs(map, y, x + 1);
        dfs(map, y, x - 1);
        dfs(map, y + 1, x);
        dfs(map, y - 1, x);
    }
}

 

저번주 풀이는 시간이 너무 오래 걸리는 편이라 리팩토링해달라는 스터디원의 의견에 새로 다시 짜왔다.