C++ में DFS का उपयोग करके द्वीपों की संख्या खोजना

समस्या विवरण

इस समस्या में, हमें एक 2D बाइनरी मैट्रिक्स दिया गया है। हमारा कार्य DFS का उपयोग करके द्वीपों की संख्या खोजना है।

द्वीप मैट्रिक्स में 1 या अधिक जुड़े 1 का समूह है।

उदाहरण

इनपुट: bin[][] = {{1, 0, 0, 0},
                   {0, 1, 0, 1},
                   {0, 0, 0, 0},
                   {0, 0, 1, 0}}
आउटपुट: 3
द्वीप हैं: bin₀₀ - bin₁₁, bin₁₃, bin₃₂

हल का दृष्टिकोण

DFS का उपयोग करके समस्या को हल करने के लिए, हम मैट्रिक्स में एक संख्या के सभी पड़ोसियों (अधिकतम 8) का पता लगाने के लिए DFS तकनीक का उपयोग करेंगे और 1 की जांच करेंगे। यदि हम एक अपर्याप्त 1 मान का सामना करते हैं, तो हम इसे मानेंगे। हम मानों पर एक जांच रखेंगे जिनका दौरा किया गया है ताकि बार-बार दौरा न हो। ऐसा करके, हम मैट्रिक्स में मौजूद द्वीपों की संख्या गिन सकते हैं।

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

#define ROW 5
#define COL 5

bool 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 dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    visited[row][col] = true;
    for (int k = 0; k < 8; ++k)
        if (canVisit(bin, row + dr[k], col + dc[k], visited))
            DFS(bin, row + dr[k], col + dc[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 << "मैट्रिक्स में मौजूद द्वीपों की संख्या है " << findIslandCount(bin);
    return 0;
}

आउटपुट

मैट्रिक्स में मौजूद द्वीपों की संख्या है 4

जटिलता विश्लेषण

• समय जटिलता: O(ROW × COL) - प्रत्येक सेल का एक बार दौरा किया जाता है
• स्पेस जटिलता: O(ROW × COL) - विज़िटेड सरणी + पुनरावर्ती स्टैक

DFS बनाम डिस्जॉइंट सेट