C++ 부울 행렬에서 가장 큰 영역의 길이 찾기: DFS 알고리즘 완벽 가이드

문제 소개

이 문제에서는 0과 1로만 구성된 n×m 크기의 2차원 행렬이 주어집니다. 우리의 목표는 부울(Boolean) 행렬에서 가장 큰 영역(region)의 길이를 찾는 것입니다.

문제 정의

어떤 셀의 값이 1이라면 그 셀은 채워진 셀(filled cell)입니다. 우리는 가로, 세로, 대각선 방향으로 서로 인접해 있는 연결된 셀들의 개수, 즉 영역의 길이를 구해야 합니다.

예시로 이해하기

입력: matrix[4][5]

{ {0, 1, 1, 0, 1},
{0, 0, 1, 1, 1},
{1, 0, 0, 0, 0},
{1, 0, 1, 0, 1} }

출력: 6

설명:

행렬에는 서로 연결된 채워진 셀들의 묶음이 여러 개 존재하며, 각 영역의 크기는 1, 2, 6입니다. 이 중 가장 큰 값인 6이 정답이 됩니다.

해결 접근 방법

이 문제를 해결하는 핵심은 행렬 전체를 순회하면서 연결된 셀들의 개수를 세는 것입니다.

이를 위해 각 셀에 대해 DFS(깊이 우선 탐색)를 수행하여 현재 셀의 모든 이웃 셀을 확인합니다. 하나의 셀에는 최대 8개의 이웃 셀이 존재할 수 있습니다. 각 셀의 방문 여부는 별도의 방문 배열(hash-map 역할)로 추적하여 같은 셀을 중복해서 탐색하지 않도록 합니다. 모든 탐색이 끝나면 방문한 셀 수의 최댓값을 반환하면 됩니다.

구현 코드

아래는 위 접근 방식을 C++로 구현한 예제입니다.

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

int isNotVisited(int M[][COL], int row, int col, bool visited[][COL]) {
    return (row >= 0) && (row < ROW) && (col >= 0 ) && (col < COL) && (M[row][col] && !visited[row][col]);
}

void depthFirstSearch(int M[][COL], int row, int col, bool visited[][COL], int& count){
    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
    visited[row][col] = true;

    for (int k = 0; k < 8; ++k) {
       if (isNotVisited(M, row + rowNbr[k], col + colNbr[k], visited)) {
          count++;
          depthFirstSearch(M, row + rowNbr[k], col + colNbr[k], visited, count);
       }
    }
}

int findLargestRegionLength(int M[][COL]) {
    bool isvisited[ROW][COL];
    memset(isvisited, 0, sizeof(isvisited));
    int maxCount = -1;
    for (int i = 0; i < ROW; ++i) {
       for (int j = 0; j < COL; ++j) {
          if (M[i][j] && !isvisited[i][j]) {
             int count = 1;
             depthFirstSearch(M, i, j, isvisited, count);
             maxCount = max(maxCount, count);
          }
       }
    }
    return maxCount;
}

int main(){
    int M[][COL] = { {0, 1, 1, 0, 1},
                     {0, 0, 1, 1, 1},
                     {1, 0, 0, 0, 0},
                     {1, 0, 1, 0, 1} };

    cout<<"The length of largest region is "<<findLargestRegionLength(M);

    return 0;
}

출력 결과

The length of largest region is 6

마무리

이 알고리즘의 시간 복잡도는 O(n×m)으로, 행렬의 모든 셀을 한 번씩만 방문하기 때문에 효율적입니다. BFS(너비 우선 탐색)를 사용해도 동일한 결과를 얻을 수 있으며, 문제 상황에 따라 적절한 탐색 기법을 선택하면 됩니다.