C++ 코딩테스트 강좌, 깊이 우선 탐색

1. 문제 설명

주어진 문제는 다음과 같습니다:

정수로 이루어진 2차원 배열(N x M)에서 가장 많은 1의 연속된 그룹의 크기를 찾는 알고리즘을 구현하시오.
그룹은 상하좌우로 연결된 1의 부분 집합으로 정의됩니다. 또한, 연속된 1이 아닌 부분은
다른 그룹으로 취급합니다.

배열의 크기 (N, M)는 1 이상 100 이하입니다.

2. 문제 분석

이 문제는 DFS(Depth-First Search) 또는 BFS(Breadth-First Search)와 같이 그래프 탐색 알고리즘을 사용하여 연결된 컴포넌트를 찾는 문제입니다. 연결된 1의 수를 세고 그룹의 최대 크기를 기록하는 방식으로 해결할 수 있습니다.

입력으로 주어지는 배열은 다음과 같은 형태로 주어질 수 있습니다:

    1 0 0 1 1
    1 1 0 0 0
    0 0 1 1 1
    0 1 0 0 0
    1 1 1 0 0

이 경우, 가장 큰 그룹의 크기는 5가 됩니다.

3. 접근 방법

깊이 우선 탐색을 사용하여 연결된 1을 찾고 세어야 합니다. DFS는 스택을 기반으로 하며, 재귀적으로 혹은 명시적으로 스택을 사용하여 구현할 수 있습니다. 다음은 문제 해결을 위한 단계입니다:

  1. 2차원 배열을 순회하면서 1을 발견하면 DFS를 실행합니다.
  2. DFS에서는 현재 위치에서 상하좌우로 이동하며 연결된 1을 탐색하고 카운트를 증가시킵니다.
  3. 탐색이 끝나면 최대 그룹 크기를 비교하여 업데이트합니다.
  4. 탐색이 완료되면 최종 최대 그룹 크기를 반환합니다.

4. 코드 구현

아래는 위의 접근 방식을 C++로 구현한 코드입니다:


#include 
#include 
#include 

using namespace std;

class Solution {
public:
    int N, M; // 배열의 크기
    vector> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우 방향

    // DFS 구현
    int dfs(int x, int y, vector>& grid) {
        if (x < 0 || x >= N || y < 0 || y >= M || grid[x][y] == 0) {
            return 0; // 경계를 벗어나거나 0인 경우
        }

        grid[x][y] = 0; // 방문 표시
        int count = 1; // 현재 1 개수 카운트

        // 네 방향으로 재귀 호출
        for (const auto& dir : directions) {
            count += dfs(x + dir[0], y + dir[1], grid);
        }

        return count;
    }

    int largestGroupSize(vector>& grid) {
        N = grid.size();
        M = grid[0].size();
        int maxSize = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 1) { // 1을 찾으면
                    int groupSize = dfs(i, j, grid); // DFS 호출
                    maxSize = max(maxSize, groupSize); // 최대 그룹 크기 갱신
                }
            }
        }

        return maxSize;
    }
};

int main() {
    Solution sol;
    vector> grid = {
        {1, 0, 0, 1, 1},
        {1, 1, 0, 0, 0},
        {0, 0, 1, 1, 1},
        {0, 1, 0, 0, 0},
        {1, 1, 1, 0, 0}
    };

    int result = sol.largestGroupSize(grid);
    cout << "가장 큰 그룹의 크기: " << result << endl;
    return 0;
}

5. 코드 설명

위의 C++ 코드는 다음과 같이 구성되어 있습니다:

  1. 변수 선언: <code>N</code>와 <code>M</code>은 배열의 크기를 저장하고, <code>directions</code>는 상하좌우 이동 방향을 배열로 정의합니다.
  2. DFS 함수: <code>dfs</code> 함수는 현재 위치에서 시작하여 연결된 1의 개수를 재귀적으로 세어줍니다. 경계 조건과 방문 여부를 체크합니다.
  3. 메인 함수: <code>largestGroupSize</code> 함수는 전체 배열을 순회하며 1을 발견할 때마다 DFS를 호출하여 그룹의 크기를 계산합니다. 최대 크기를 갱신하여 최종 결과를 반환합니다.

6. 테스트 및 결과

위의 코드를 통해 다양한 테스트를 진행해 볼 수 있습니다. 예를 들어, 그룹의 크기를 변경하거나 새로운 그룹 구조를 추가하여 다양한 결과를 확인할 수 있습니다.

성공적인 결과는 다음과 같습니다:

가장 큰 그룹의 크기: 5

7. 시간 복잡도 분석

이 알고리즘은 O(N * M) 시간 복잡도를 가집니다. 각 셀을 한 번씩 방문하기 때문입니다. 또한 메모리 복잡도는 O(N * M)으로 배열과 재귀 호출 스택에 필요합니다.

8. 마무리

이번 강좌에서는 깊이 우선 탐색을 사용하여 연결된 1의 최대 그룹 크기를 찾는 문제를 해결하였습니다. DFS는 경로 탐색 문제나 연결 성분 찾기에 매우 유용한 알고리즘으로, 많은 알고리즘 문제에서 활용될 수 있습니다.

다음에는 BFS에 대해 알아보고, 다양한 응용 문제를 풀어보겠습니다. 감사합니다!