[BOJ] 숫자 정사각형 - 1051 (S3)

시간 제한	메모리 제한
2 초	128 MB

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 넓이를 출력한다.

풀이

이 문제는 브루트포스 알고리즘으로 해결할 수 있는 문제이다. 가능한 모든 정사각형을 확인하여 네 꼭짓점의 값이 같은 가장 큰 정사각형을 찾으면 된다.

접근 방법

정사각형의 한 변의 길이를 k라고 하면, 정사각형의 네 꼭짓점은 다음과 같다:

• 좌상단: (y, x)
• 우상단: (y, x + k)
• 좌하단: (y + k, x)
• 우하단: (y + k, x + k)

가장 큰 정사각형을 찾아야 하므로, 큰 정사각형부터 확인하는 것이 효율적이다. 정사각형의 최대 크기는 min(N-1, M-1)이 되며, 이는 직사각형의 크기에 의해 결정된다.

풀이 과정

1. 가능한 최대 정사각형 크기부터 시작하여 크기를 줄여가며 확인한다.
2. 각 크기 k에 대해 가능한 모든 시작 위치 (x, y)를 탐색한다.
3. 네 꼭짓점의 값이 모두 같은 정사각형을 찾으면 바로 종료한다.
4. 정사각형의 넓이는 (k+1)²이다. (k는 인덱스 차이이므로 실제 길이는 k+1)

최적화

가장 큰 정사각형부터 확인하므로, 조건을 만족하는 정사각형을 찾는 즉시 탐색을 종료할 수 있다. 이를 위해 중첩된 for 문을 빠져나가기 위한 break-else 패턴을 사용하였다.

코드

N, M = map(int, input().split())

rectangle = [list(input()) for _ in range(N)]

len_limit = min(N - 1 , M - 1)

ans = 0
for k in range(len_limit, -1, -1):
    # print(k)
    for x in range(M - k):
        for y in range(N - k):
            # print(x, y, k)
            if rectangle[y][x] == rectangle[y + k][x] == rectangle[y][x + k] == rectangle[y + k][x + k]:
                ans = k
                break
        else:
            continue
        break
    else:
        continue
    break

print((ans + 1) ** 2)

코드 설명

• len_limit = min(N - 1, M - 1): 가능한 최대 정사각형의 한 변 길이 (인덱스 차이)
• for k in range(len_limit, -1, -1): 큰 정사각형부터 확인
• for x in range(M - k): 정사각형의 시작 x 좌표 (x + k가 범위를 벗어나지 않도록)
• for y in range(N - k): 정사각형의 시작 y 좌표 (y + k가 범위를 벗어나지 않도록)
• 네 꼭짓점 비교: rectangle[y][x] (좌상), rectangle[y + k][x] (좌하), rectangle[y][x + k] (우상), rectangle[y + k][x + k] (우하)
• break-else 패턴: 조건을 만족하는 정사각형을 찾으면 모든 반복문을 빠져나감

시간 복잡도

최악의 경우 모든 가능한 정사각형을 확인해야 하므로 시간 복잡도는 O(N × M × min(N, M))이다.

N, M ≤ 50이므로 최악의 경우에도 50 × 50 × 50 = 125,000번의 연산으로 충분히 시간 내에 해결할 수 있다.

주의 사항

• 정사각형의 한 변의 길이는 k+1이므로 넓이는 (k+1)²이다.
• 인덱스가 범위를 벗어나지 않도록 주의해야 한다.
• 가장 큰 정사각형을 찾았을 때 즉시 탐색을 종료하여 불필요한 연산을 줄일 수 있다.