문제 소개
이 문제에서는 NxN 크기의 이진 행렬 bin[][]이 주어집니다. 우리의 과제는 이 행렬 안에서 1로만 구성된 가장 큰 '+'(십자) 모양의 크기를 찾는 것입니다.
구체적인 예시를 통해 문제를 먼저 이해해 보겠습니다.
입력
0 1 1 1 1 1 0 1 0
출력
5
위 예시에서 행렬 중앙의 1을 중심으로 상하좌우 네 방향으로 각각 한 칸씩 뻗어 나간 십자 모양을 만들 수 있으므로, 전체 크기는 5가 됩니다.
해결 접근 방법
이 문제의 핵심 아이디어는 다음과 같습니다. 어떤 지점을 중심으로 만들 수 있는 '+'의 크기는, 그 지점에서 위·아래·왼쪽·오른쪽 네 방향으로 연속된 1의 개수 중 최솟값으로 결정됩니다. 네 방향 중 어느 하나라도 짧으면 그 지점까지만 십자 모양을 확장할 수 있기 때문입니다.
이를 효율적으로 처리하기 위해 각 방향마다 하나씩, 총 4개의 보조 행렬을 생성합니다. 각 보조 행렬은 해당 칸을 기준으로 특정 방향으로 연속된 1의 개수를 저장합니다. 이후 모든 좌표에 대해 네 방향 값의 최솟값을 계산하고, 그중 최댓값을 찾으면 가장 큰 '+'의 한쪽 팔 길이를 얻을 수 있습니다.
마지막으로 전체 크기는 4 × (팔 길이 − 1) + 1 공식으로 구할 수 있습니다. 이 방법의 시간 복잡도와 공간 복잡도는 모두 O(N²)입니다.
솔루션의 동작을 보여주는 프로그램입니다.
예제 코드
#include <iostream>
using namespace std;
#define N 7
int findLargestPlusSize(int mat[N][N]) {
int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
for (int i = 0; i < N; i++) {
conOneTop[0][i] = mat[0][i];
conOneBottom[N - 1][i] = mat[N - 1][i];
conOneLeft[i][0] = mat[i][0];
conOneRight[i][N - 1] = mat[i][N - 1];
}
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (mat[i][j] == 1)
conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
else
conOneLeft[i][j] = 0;
if (mat[j][i] == 1)
conOneTop[j][i] = conOneTop[j - 1][i] + 1;
else
conOneTop[j][i] = 0;
j = N - 1 - j;
if (mat[j][i] == 1)
conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
else
conOneBottom[j][i] = 0;
if (mat[i][j] == 1)
conOneRight[i][j] = conOneRight[i][j + 1] + 1;
else
conOneRight[i][j] = 0;
j = N - 1 - j;
}
}
int maxConOne = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++){
int ConOnes = min(min(conOneTop[i][j],
conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
if(ConOnes > maxConOne)
maxConOne = ConOnes;
}
}
if (maxConOne)
return (4 * (maxConOne - 1) + 1);
return 0;
}
int main() {
int mat[N][N] = {
{ 1, 0, 1, 1, 1, 1, 0 },
{ 1, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
};
cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
return 0;
}출력
The size of the largest plus formed by ones is 9
위 프로그램은 7×7 입력 행렬에서 1로 구성된 가장 큰 '+'의 크기가 9임을 출력합니다. 즉, 중심을 포함하여 한 방향당 길이 3짜리 팔이 네 방향으로 뻗어 나간 십자 모양이 존재한다는 의미입니다.