(Leetcode) 200 - Number of Islands
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/number-of-islands/description/
그래프 문제로 분류되어 있는데 배열문제에 가깝지 않나 싶다. (실제로 토픽도 배열로 정리되어 있다.)
2차원 배열(grid)에서 1인 부분을 찾았을 때, 주변 영역을 0으로 만들어서 중복 카운트를 하도록 하는 컨셉이 재밌었다.
class Solution {
int w;
int h;
public int numIslands(char[][] grid) {
int count = 0;
w = grid.length;
h = grid[0].length;
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
if (grid[i][j] == '1') {
dfs(grid, i,j);
count++;
}
}
}
return count;
}
public void dfs(char[][] grid, int i, int j) {
if(i < 0 || i >= w || j < 0 || j >= h || 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);
}
}
TC, SC
코드에 정의한 대로 grid의 길이를 w, grid[0]의 길이를 h로 정의했을 때, 이 코드의 시간 복잡도는 O(w * h), 공간 복잡도는 O(w * h) 이다.