C++로 이진 행렬에서 1로 이루어진 도형의 둘레 구하기

이 문제에서는 0과 1로만 구성된 크기 n×m의 이진 행렬 bin[][]이 주어집니다. 우리의 목표는 이진 행렬에서 1들이 만드는 도형의 둘레(perimeter)를 구하는 것입니다.

여기서 둘레란 도형을 모든 방향에서 둘러싸는 경계의 길이를 의미합니다. 예를 들어, 값이 하나뿐인 경우 둘레는 4가 됩니다.

예제로 문제 이해하기

입력

bin[][] = [1, 0]
   [1, 0]

출력

6

설명

셀 (0,0)과 (1,0)이 서로 연결되어 가로 2, 세로 1인 직사각형을 형성합니다. 따라서 둘레는 2×(2+1) = 6이 됩니다.

해결 접근 방법

가장 간단한 해결 방법은 행렬의 모든 1을 찾아 각각이 둘레에 기여하는 값을 계산한 후, 이를 모두 더하는 것입니다.

행렬에서 하나의 1이 둘레에 기여할 수 있는 값은 다음과 같습니다.

• 최대 기여도는 4: 해당 1이 인접한 1 없이 홀로 존재할 때입니다.
• 최소 기여도는 0: 해당 1이 상하좌우 네 방향 모두 1로 둘러싸여 있을 때입니다.

따라서 행렬의 각 요소를 순회하며 값이 1인지 확인하고, 1이라면 상하좌우의 이웃 셀을 검사하여 둘레에 대한 기여도를 계산합니다. 각 1의 기여도는 (4 - 인접한 1의 개수)로 구할 수 있으며, 이 값을 모두 합산하면 전체 둘레가 됩니다.

구현 예제

#include<iostream>
using namespace std;
#define R 3
#define C 5
int contibutionToPerimeter(int mat[][C], int i, int j) {
    int neighbours = 0;
    if (i > 0 && mat[i - 1][j])
        neighbours++;
    if (j > 0 && mat[i][j - 1])
        neighbours++;
    if (i < R-1 && mat[i + 1][j])
        neighbours++;
    if (j < C-1 && mat[i][j + 1])
        neighbours++;
    return (4 - neighbours);
}
int calcPerimeter(int mat[R][C]){
    int perimeter = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (mat[i][j] == 1)
                perimeter += contibutionToPerimeter(mat, i ,j);
    return perimeter;
}
int main() {
    int mat[R][C] = { {0, 1, 0, 0, 0},
    {1, 1, 1, 1, 0},
    {1, 1, 0, 1, 1} };
    cout<<"The perimeter of shapes from formed with 1s is "<<calcPerimeter(mat);
    return 0;
}

출력

The perimeter of shapes from formed with 1s is 18

코드 설명

contibutionToPerimeter() 함수는 특정 셀 (i, j)가 둘레에 기여하는 값을 반환합니다. 함수 내부에서는 해당 셀의 상, 하, 좌, 우 네 방향을 검사하여 인접한 1의 개수를 세고, 4에서 그 개수를 뺀 값을 반환합니다. 행렬의 가장자리에 있는 셀은 범위를 벗어나지 않도록 조건문으로 처리됩니다.

calcPerimeter() 함수는 행렬 전체를 이중 반복문으로 순회하면서 값이 1인 셀마다 기여도를 누적합산하여 최종 둘레를 계산합니다.

이 알고리즘의 시간 복잡도는 O(n×m)으로, 행렬의 모든 셀을 한 번씩만 검사하면 되기 때문에 효율적입니다.