백준 1051번 [숫자 정사각형](C++) -yes6686- 티스토리

백준 문제 풀이: 1051 [숫자 정사각형]

---

문제 링크: https://www.acmicpc.net/problem/1051

문제 설명:

n×m 크기의 숫자 격자가 주어질 때, 네 꼭짓점이 모두 같은 숫자인 가장 큰 정사각형의 넓이를 구하는 문제입니다. 정사각형의 크기는 1×1부터 시작하며, 네 꼭짓점이 같은 조건을 만족해야 합니다.

---

문제 해결 코드

// 백준 1051 - 숫자 정사각형
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector grid(n); // 숫자 격자를 저장할 벡터
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    int maxSize = 1; // 정사각형의 최대 크기 (최소 1×1)
    
    // 모든 좌표를 순회하며 가능한 정사각형 크기를 확인
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 정사각형의 크기를 늘려가며 확인
            for (int k = 1; i + k < n && j + k < m; k++) {
                if (grid[i][j] == grid[i + k][j] && 
                    grid[i][j] == grid[i][j + k] && 
                    grid[i][j] == grid[i + k][j + k]) {
                    int size = (k + 1) * (k + 1); // 정사각형 넓이
                    maxSize = max(maxSize, size);
                }
            }
        }
    }

    cout << maxSize << '\n'; // 결과 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 격자의 모든 좌표를 순회하며 가능한 정사각형의 크기를 점진적으로 확인합니다.
  • 네 꼭짓점이 같은 숫자인 경우만 정사각형의 크기를 갱신합니다.
• 구현 세부사항:
  • 입력된 격자를 string 형태로 저장하여 간단히 처리합니다.
  • 내부 반복문에서 정사각형의 크기를 늘려가며 네 꼭짓점을 비교합니다.
• 시간 복잡도 분석:
  • 전체 반복문: O(n ⋅ m ⋅ min(n, m))
  • 최악의 경우 약 O(n³)에 해당합니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!