C++ DFS로 이진 행렬에서 섬의 개수 찾기

이 문제에서는 2차원 이진 행렬이 주어지며, DFS(깊이 우선 탐색)를 사용해 섬의 개수를 찾아야 합니다.

섬(Island)이란 행렬 안에서 가로, 세로, 대각선 방향으로 서로 연결된 하나 이상의 1들이 모여 이루어진 영역을 말합니다.

문제 이해하기

예제를 통해 문제를 살펴보겠습니다.

입력 : bin[][] = {{ 1 0 0 0}
    {0 1 0 1}
    {0 0 0 0}
    {0 0 1 0}}
출력 : 3

설명:

섬은 다음과 같이 구성됩니다.

bin₀₀ – bin₁₁ (대각선으로 연결된 하나의 섬)
bin₁₃
bin₃₂

즉, (0,0)과 (1,1)은 대각선 방향으로 인접하므로 같은 섬에 속하고, 나머지 두 개의 1은 각각 독립된 섬이 됩니다.

해결 접근 방식

DFS로 이 문제를 해결하려면, 행렬의 각 원소에 대해 인접한 최대 8개의 이웃 칸을 탐색하며 값이 1인지 확인합니다. 아직 방문하지 않은 1을 발견하면 그 지점을 새로운 섬의 시작점으로 간주하고, 해당 지점에서 DFS를 수행해 연결된 모든 1들을 방문 처리합니다.

이때 이미 방문한 칸을 다시 탐색하지 않도록 방문 여부(visited 배열)를 관리하면, 행렬 전체를 한 번씩만 확인하면서 섬의 총개수를 정확히 셀 수 있습니다. 그래프 자료구조와 그래프에서의 DFS 동작 원리를 미리 이해하고 있다면 더욱 쉽게 접근할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 4

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 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, false, 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;
}

실행 결과

행렬에 존재하는 섬의 개수는 3

복잡도 분석

시간 복잡도: O(ROW × COL) — 행렬의 모든 칸을 최대 한 번씩만 방문합니다.
공간 복잡도: O(ROW × COL) — 방문 여부를 저장하는 배열과 재귀 호출 스택이 필요합니다.

마무리

DFS를 활용하면 연결 요소(connected component)의 개수를 효율적으로 구할 수 있습니다. 이 문제는 그래프의 연결 요소 탐색을 2차원 격자(grid) 형태로 응용한 대표적인 유형으로, BFS나 Union-Find 알고리즘으로도 동일하게 해결할 수 있습니다.