C++로 이진 행렬에서 1로 둘러싸인 0의 개수 구하기

이 튜토리얼에서는 C++을 사용해 이진 행렬(binary matrix)에서 1로 둘러싸여 차단된 0의 개수를 구하는 프로그램을 다룹니다.

0과 1로만 이루어진 이진 행렬이 주어졌을 때, 우리의 목표는 1에 의해 완전히 둘러싸여 행렬의 경계와 연결되지 않은 모든 0을 찾아 그 개수를 세는 것입니다.

접근 방법

이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 행렬의 네 가장자리(첫 번째 행, 마지막 행, 첫 번째 열, 마지막 열)에 위치한 0에서 DFS를 시작합니다.
2. DFS를 통해 경계에서 도달할 수 있는 모든 0을 방문 표시(값을 1로 변경)합니다.
3. 탐색이 끝난 후에도 여전히 0으로 남아 있는 칸은 1로 완전히 둘러싸인 칸입니다. 이들의 개수를 세면 정답이 됩니다.

예제

#include <iostream>
using namespace std;
#define Row 4
#define Col 5
int r[4] = { 0, 0, 1, -1 };
int c[4] = { 1, -1, 0, 0 };
bool isSafe(int x, int y, int M[][Col]) {
    if (x >= 0 && x <= Row && y >= 0 &&
        y <= Col && M[x][y] == 0)
        return true;
    return false;
}
//행렬에서 DFS 수행
void DFS(int x, int y, int M[][Col]) {
    //노드를 방문한 것으로 표시
    M[x][y] = 1;
    for (int k = 0; k < 4; k++)
        if (isSafe(x + r[k], y + c[k], M))
            DFS(x + r[k], y + c[k], M);
}
//차단된 0의 개수 반환
int CountAllZero(int M[][Col]){
    for (int i = 0; i < Col; i++)
        if (M[0][i] == 0)
            DFS(0, i, M);
    for (int i = 0; i < Col; i++)
        if (M[Row - 1][i] == 0)
            DFS(Row - 1, i, M);
    for (int i = 0; i < Row; i++)
        if (M[i][0] == 0)
            DFS(i, 0, M);
    for (int i = 0; i < Row; i++)
        if (M[i][Col - 1] == 0)
            DFS(i, Col - 1, M);
//1로 둘러싸인 모든 0의 개수 계산
int result = 0;
for (int i = 0; i < Row; i++)
    for (int j = 0; j < Col; j++)
        if (M[i][j] == 0)
            result++;
    return result;
}
int main(){
    int M[][Col] = { { 1, 1, 1, 0, 1 },{ 1, 0, 0, 1, 0 },{ 1, 0, 1, 0, 1 },{ 0, 1, 1, 1, 1 } };
    cout << CountAllZero(M) << endl;
    return 0;
}

출력

4

코드 설명

isSafe() 함수는 다음에 탐색할 위치가 행렬 범위 안에 있고 해당 칸의 값이 0인지 확인합니다. DFS() 함수는 현재 칸을 방문 처리한 뒤, 상하좌우 네 방향으로 재귀적으로 탐색을 이어갑니다.

CountAllZero() 함수는 먼저 행렬의 네 가장자리에 있는 0에서 DFS를 수행해 외부와 연결된 모든 0을 제거합니다. 그다음 탐색이 끝난 뒤에도 남아 있는 0의 개수를 세어 반환하는데, 이 값이 곧 1로 둘러싸인 0의 개수입니다.

위 예제에서 실행 결과는 4로, 행렬 내부에 1로 둘러싸여 외부와 연결되지 않은 0이 총 4개 있음을 의미합니다.