섬 수 LeetCode 솔루션


자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 DocuSign의 Facebook 골드만 삭스 구글 과연 링크드 인 리프트 Microsoft 신탁 세일즈 포스 SAP ServiceNow 동네 짱 Yandex 주차
리트코드 LeetCodeSolutions 감독자 Tik의 톡조회수 51

문제 정책

또한 섬의 수 LeetCode 솔루션 – "섬 수"는 귀하가 g임을 나타냅니다.'2'(땅)과 '1'(물)의 지도를 나타내는 mxn 0D 이진 그리드라도 섬의 수를 반환해야 합니다. 섬은 물로 둘러싸여 있으며 인접한 육지를 수평 또는 수직으로 연결하여 형성됩니다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

섬 수 LeetCode 솔루션

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
3

설명 : 위 그림에서 강조 표시된 섬을 볼 수 있습니다. 보시다시피 세 개의 섬이 있습니다.

참고: 다른 색상은 위 이미지에서 다른 섬을 나타냅니다.

접근

아이디어 :

우리는 모든 순회 DFS를 사용할 수 있습니다. BFS 이 문제를 해결하기 위해(Number of Islands LeetCode Solution). 우리는 또한 우리가 이미 방문한 땅을 추적할 "visited"라는 배열을 유지할 것입니다. 그래서 우리는 먼저 섬의 수를 저장할 "answer"라는 변수를 XNUMX으로 초기화할 것입니다. 

그리드의 모든 토지를 하나씩 횡단합니다. 횡단하는 동안 아직 방문하지 않은 땅을 찾으면 새 섬을 찾았음을 의미하며 "ans"를 늘리고 DFS 또는 BFS를 사용하여 연결된 모든 땅을 방문한 것으로 표시합니다.

연산:

우리는 "visited"라는 어레이를 유지할 것입니다. 

  1. 부울 배열 초기화 모든 값이 false인 "방문"입니다. 또한 "ans"라는 변수를 XNUMX으로 초기화하여 답을 저장합니다.
  2. 그리드의 각 요소를 통과합니다.
  3. 그것이 토지이고 아직 방문하지 않았는지 확인하십시오. "ans"를 1만큼 늘리고 해당 요소에서 순회(BFS 또는 DFS)를 시작하십시오.

암호

섬 수의 C++ 프로그램:

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool check(int x, int y, int n, int m)
{
   return x >= 0 and y >= 0 and x < n and y < m;
}
void dfs(vector<vector<char>> &grid, vector<vector<bool>> &vis, int x, int y, int n, int m)
{
   if (!check(x, y, n, m) or grid[x][y] == '0' or vis[x][y] == true)
   {
       return;
   }
   vis[x][y] = true;
   for (auto ele : dir)
   {
       int x1 = x + ele.first;
       int y1 = y + ele.second;
       dfs(grid, vis, x1, y1, n, m);
   }
}
int numIslands(vector<vector<char>> &grid)
{
   int ans = 0;
   int n = grid.size();
   int m = grid[0].size();
   vector<vector<bool>> vis(n, vector<bool>(m, false));
   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j < m; j++)
       {
           if (vis[i][j] == false and grid[i][j] == '1')
           {
               ans++;
               dfs(grid, vis, i, j, n, m);
           }
       }
   }
   return ans;
}
int main()
{
   vector<vector<char>> grid = {
       {'1', '1', '0', '0', '0'},
       {'1', '1', '0', '0', '0'},
       {'0', '0', '1', '0', '0'},
       {'0', '0', '0', '1', '1'}};
   cout << numIslands(grid) << endl;
   return 0;
}
3

섬 수의 JAVA 프로그램:

public class TutorialCup
{
    static int dir[][]={{-1,0},{0,-1},{1,0},{0,1}};
    public static boolean check(int x,int y,int n,int m){
        return x>=0 && y>=0 && x<n && y<m;
    }
    public static void dfs(char[][] grid,boolean vis[][],int x,int y,int n,int m ){
        if(!check(x,y,n,m) || grid[x][y]=='0' || vis[x][y]==true){
            return;
        }
        vis[x][y]=true;
        for(int i=0;i<4;i++){
            int x1=x+dir[i][0];
            int y1=y+dir[i][1];
            dfs(grid,vis,x1,y1,n,m);
        }
    }
    public static int numIslands(char[][] grid) {
        int ans=0;
        int n=grid.length;
        int m=grid[0].length;
        boolean vis[][]=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(vis[i][j]==false && grid[i][j]=='1'){
                    ans++;
                    dfs(grid,vis,i,j,n,m);
                }
            }
        }
        return ans;
    }
  public static void main(String[] args) {
    char grid[][]={
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}};
        System.out.println(numIslands(grid));
  }
}
3

섬 개수에 대한 복잡성 분석 LeetCode 솔루션

섬 개수에 대한 시간 복잡도 LeetCode 솔루션

위 코드의 시간 복잡성은 O (n * m) 그리드의 각 요소를 항상 한 번 순회하기 때문입니다. 여기서 n과 m은 행 수 및 열 수 각각.

섬 개수에 대한 공간 복잡도 LeetCode 솔루션

위 코드의 공간 복잡성은 다음과 같습니다. O (n * m) 2D 배열을 사용하여 토지를 방문했는지 여부를 저장하기 때문입니다.

참조 – https://en.wikipedia.org/wiki/Breadth-first_search

코멘트를 남겨

Translate »
1