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

문제

1051번: 숫자 정사각형

문제

문제

문제

문제 이해

• N * M 크기의 직사각형 (N : 세로, M : 가로)
• 꼭짓점에 쓰여 있는 수가 모두 같고, 크기가 가장 큰 정사각형을 찾아라

풀이

직사각형의 숫자를 2차원 리스트로 저장한 후 모든 숫자를 순회하며, 조건에 맞는 정사각형을 찾도록 구현해 보자.
시간제한이 2초이며, N, M <= 50으로 넉넉한 시간을 가지고 있다. 그래서 다소 시간 복잡도가 높더라도 올바르게 작동만 한다면 정답을 받을 수 있을 것이라 생각했다.

1. 2차원 리스트 형태로 숫자를 입력
2. result (반환해 줄 직사각형의 크기)를 1로 초기화
3. 첫 숫자부터 차례로 순회
   1. 가로로 진행하며 같은 숫자가 있는지 확인
   2. 같은 숫자가 없다면, 다음 숫자로 넘어감 (M보다 작을 때까지 진행)
   3. 같은 숫자가 있다면, 길이를 구해 세로 아래에 같은 숫자가 존재하는지 확인 (N보다 작을 경우)
4. result를 갱신하며 최댓값을 반환

코드

• left_top을 지정한 뒤 해당 숫자로 이루어진 정사각형이 존재하는지 확인
• 모든 숫자를 순회하며, 같은 숫자가 있다면 정사각형인지 모두 확인
• 정확하지는 않지만, 시간 복잡도가 O (N^2 * M) 정도로 복잡함

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
rec = [input().rstrip() for _ in range(n)]

result = 1

for i in range(n):
    for j in range(m):
        left_top = rec[i][j]
        for k in range(j + 1, m):
            if left_top == rec[i][k]:
                diff_ind = k - j
                if i + diff_ind < n and left_top == rec[i + diff_ind][j] and left_top == rec[i + diff_ind][k]:
                    if (diff_ind + 1) ** 2 > result:
                        result = (diff_ind + 1) ** 2

print(result)