백준 1051번 숫자 정사각형 C++ 풀이

🔷 백준 1051번 숫자 정사각형 C++ 풀이

✅ 문제

N×M 크기의 직사각형 격자 안에 한 자리 숫자가 적혀 있습니다. 이 격자에서 네 꼭짓점에 적힌 숫자가 모두 같은 가장 큰 정사각형을 찾고, 그 넓이를 구하는 문제입니다. 정사각형은 반드시 행과 열에 평행하게만 만들어야 합니다.

✅ 입력

• 첫째 줄: N, M (1 ≤ N,M ≤ 50)
• 둘째 줄부터 N개의 줄: 길이 M의 숫자가 공백 없이 주어짐

✅ 출력

네 꼭짓점이 모두 같은 가장 큰 정사각형의 넓이

✅ 예제 입력

42101
22100
22101
    

✅ 예제 출력

9
    

✅ 아이디어

이 문제를 해결하기 위해 i,j로 격자 안을 옮겨가며 탐색하고, k를 늘려가며 정사각형의 크기를 키워 탐색하는 방식을 사용합니다. 즉, i,j로 “위치”를 옮기고, k로 “크기”를 키우며 탐색하는 이중 구조입니다.

✅ 1️⃣ i,j로 현재 정사각형 위치를 옮겨가며 탐색

가장 작은 정사각형인 2×2(즉, k=1)부터 시작합니다. i,j는 왼쪽 위 꼭짓점의 좌표입니다. i,j를 격자 안에서 가능한 모든 위치로 옮겨가며, 현재 크기의 정사각형이 가능한지 확인합니다.

예를 들어, k=1(2×2)일 때는 아래처럼 i,j가 옮겨 다니며 탐색합니다.

왼쪽 위 첫 번째 위치:

[4 2] 1 0 1
[2 2] 1 0 0
 2 2 1 0 1
    

오른쪽으로 한 칸 이동:

4 [2 1] 0 1
2 [2 1] 0 0
2 2 1 0 1
    

다시 오른쪽으로 이동:

4 2 [1 0] 1
2 2 [1 0] 0
2 2 1 0 1
    

한 행을 끝까지 탐색한 뒤, i를 한 칸 내려 다시 왼쪽부터 탐색합니다:

 4 2 1 0 1
[2 2] 1 0 0
[2 2] 1 0 1
    

다시 오른쪽으로 옮깁니다:

 4 2 1 0 1
2 [2 1] 0 0
2 [2 1] 0 1
    

✅ 2️⃣ k를 증가시켜 크기를 키우며 탐색

k=1(2×2)로 격자 전체를 탐색한 후, k=2(3×3)로 크기를 키웁니다. k가 증가할수록 정사각형의 크기가 커지고, 탐색 가능한 i,j의 범위는 줄어듭니다. k=2(3×3)일 때도 같은 방식으로 i,j를 옮겨가며 탐색합니다.

왼쪽 위 첫 번째 위치:

[4 2 1] 0 1
[2 2 1] 0 0
[2 2 1] 0 1
    

i,j를 오른쪽으로 옮깁니다:

4 [2 1 0] 1
2 [2 1 0] 0
2 [2 1 0] 1
    

이처럼 k를 1씩 늘려가며 더 큰 정사각형을 시도합니다. 더 이상 네 꼭짓점이 모두 같은 정사각형이 없으면 그 전 크기가 최대 크기입니다.

✅ 3️⃣ 네 꼭짓점이 같은지 확인

각각의 i,j와 k가 정해졌을 때, 해당 정사각형의 꼭짓점 네 칸이 모두 같은지를 검사합니다. 꼭짓점 좌표는 다음과 같습니다:

• 왼쪽 위: (i,j)
• 오른쪽 위: (i,j+k)
• 왼쪽 아래: (i+k,j)
• 오른쪽 아래: (i+k,j+k)

예를 들어, k=1일 때 다음 위치는 네 꼭짓점이 같아 유효합니다:

[2 2] 1 0 1
[2 2] 1 0 0
 2 2 1 0 1
    

✅ 전체 코드

#include <iostream>
using namespace std;

int main() {
    int N, M, max_k = 0;
    int arr[51][51];
    char line[51];

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> line;
        for (int j = 0; j < M; j++) {
            arr[i][j] = line[j] - '0';
        }
    }

    int min_n = (N < M ? N : M);

    for (int k = 0; k < min_n; k++) {
        for (int i = 0; i + k < N; i++) {
            for (int j = 0; j + k < M; j++) {
                if (arr[i][j] == arr[i][j+k] &&
                    arr[i][j] == arr[i+k][j] &&
                    arr[i][j] == arr[i+k][j+k]) {
                    if (k > max_k) max_k = k;
                }
            }
        }
    }

    cout << (max_k+1)*(max_k+1) << endl;
    return 0;
}
    

✅ 개별 코드 설명 (아이디어 + 다이어그램)

🔷 1️⃣ 입력 처리 및 배열 초기화

cin >> N >> M;
for (int i = 0; i < N; i++) {
    cin >> line;
    for (int j = 0; j < M; j++) {
        arr[i][j] = line[j] - '0';
    }
}
    

📌 아이디어: 문자열로 입력된 한 줄(line)을 받아서 int 배열(arr)로 변환합니다. 즉, 이렇게 생긴 입력을:

42101
22100
22101
    

다음과 같은 2차원 배열에 채웁니다:

4 2 1 0 1
2 2 1 0 0
2 2 1 0 1
    

🔷 2️⃣ 최대 크기 후보 계산

int min_n = (N < M ? N : M);
    

📌 아이디어: 가장 큰 정사각형은 격자의 작은 쪽 길이를 넘지 못합니다. 예를 들어 3×5 격자에서는 최대 3×3 정사각형까지만 가능합니다.

🔷 3️⃣ k와 i,j를 늘리며 탐색

for (int k = 0; k < min_n; k++) {
    for (int i = 0; i + k < N; i++) {
        for (int j = 0; j + k < M; j++) {
            if (arr[i][j] == arr[i][j+k] &&
                arr[i][j] == arr[i+k][j] &&
                arr[i][j] == arr[i+k][j+k]) {
                if (k > max_k) max_k = k;
            }
        }
    }
}
    

📌 아이디어:

• k는 현재 정사각형의 크기(k+1)입니다.
• i,j는 왼쪽 위 꼭짓점입니다.
• 격자 안에서 정사각형이 오른쪽, 아래로 벗어나지 않는 범위에서만 탐색합니다.

📌 실제 탐색 예시: k=1(2×2)일 때 (i=0,j=0) 기준으로 탐색하면:

[4 2] 1 0 1
[2 2] 1 0 0
 2 2 1 0 1
    

j를 한 칸 오른쪽으로 옮기면:

4 [2 1] 0 1
2 [2 1] 0 0
2 2 1 0 1
    

j를 끝까지 다 옮기고 나면 i를 한 칸 아래로 내려가고 다시 j를 왼쪽부터 탐색합니다:

 4 2 1 0 1
[2 2] 1 0 0
[2 2] 1 0 1
    

k를 증가시켜 k=2(3×3)로 탐색할 때는 다음처럼 더 큰 범위를 검사합니다:

[4 2 1] 0 1
[2 2 1] 0 0
[2 2 1] 0 1
    

이처럼 k가 커질수록 정사각형이 커지고, i,j의 탐색 범위는 좁아집니다.

🔷 4️⃣ 넓이 계산 및 출력

cout << (max_k+1)*(max_k+1) << endl;
    

📌 아이디어: max_k+1은 찾은 가장 큰 정사각형의 한 변의 길이입니다. 넓이는 길이×길이입니다.

✅ 결론

• 격자 전체를 i,j로 옮겨가며 현재 크기의 정사각형을 탐색합니다.
• k를 늘리며 정사각형의 크기를 키워가며 탐색합니다.
• 네 꼭짓점이 모두 같은지를 비교해 유효성을 확인합니다.
• 가장 큰 정사각형의 넓이를 출력합니다.