C++에서 DFS를 사용하여 섬의 수 찾기

이 문제에서는 2D 이진 행렬이 제공됩니다. 우리의 임무는 DFS를 사용하여 섬의 수를 찾는 것입니다.

섬 매트릭스에서 하나 이상의 연결된 1의 접지입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : bin[][] = {{ 1 0 0 0}
   {0 1 0 1}
   {0 0 0 0}
   {0 0 1 0}}
Output : 3
Explanation
Islands are −bin00 - bin11
bin13
bin32

솔루션 접근 방식

DFS를 사용하여 문제를 해결하기 위해 DFS 기술을 사용하여 모든 이웃(행렬에서 가능한 최대 8개)을 탐색하고 1을 확인합니다. 방문하지 않은 값이 1개 있으면 이를 고려합니다. 재방문을 피하기 위해 방문한 값은 계속 체크하도록 하겠습니다. 이렇게 하면 행렬에 있는 섬의 수를 셀 수 있습니다.

그래프에서 DFS 알아보기

그래프에 대해 알아보기

예시

#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
int canVisit(int bin[][COL], int row, int col, bool visited[][COL]){
   return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (bin[row][col] && !visited[row][col]);
}
void DFS(int bin[][COL], int row, int col, bool visited[][COL]){
   static int getNeighbourRow[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
   static int getNeighbourCol[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
   visited[row][col] = true;
   for (int k = 0; k < 8; ++k)
      if (canVisit(bin, row + getNeighbourRow[k], col + getNeighbourCol[k], visited))
         DFS(bin, row + getNeighbourRow[k], col + getNeighbourCol[k], visited);
}
int findIslandCount(int bin[][COL]){
   bool visited[ROW][COL];
   memset(visited, 0, sizeof(visited));
   int islandCount = 0;
   for (int i = 0; i < ROW; ++i)
   for (int j = 0; j < COL; ++j)
   if (bin[i][j] && !visited[i][j]) {
      DFS(bin, i, j, visited);
      islandCount++;
   }
   return islandCount;
}
int main(){
   int bin[][COL] = {{1, 0, 0, 0},
   {0, 1, 0, 1},
   {0, 0, 0, 0},
   {0, 0, 1, 0}};
   cout<<"The number of islands present in the matrix is "<<findIslandCount(bin);
   return 0;
}

출력

The number of islands present in the matrix is 4