🥚문제

https://www.acmicpc.net/problem/1051

• 구현
• 브루트포스 알고리즘

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, list(input().strip()))) for _ in range(N)]

# 정사각형의 한 변의 길이가 될 수 있는 최대
max_side = min(M, N)

ans = 1
for r in range(N):
    for c in range(M):
        # (r, c)가 좌측 상단 꼭짓점일 때,
        # (r, c)와 나머지 세 꼭짓점이 같은 숫자인지 확인한다
        for i in range(1, max_side):
            if 0 <= r + i < N and 0 <= c + i < M:
                if arr[r][c] == arr[r+i][c] == arr[r][c+i] == arr[r+i][c+i]:
                    ans = max(ans, (i+1)*(i+1))

print(ans)

---

🧂아이디어

구현

• 입력으로 받은 2차원 리스트 arr을 순회하면서 좌표 (r, c)가 좌측 상단 꼭짓점일 때 나머지 세 꼭짓점과 값이 같은지 확인한다.

• 이때, N*M의 직사각형 내에서 만들 수 있는 정사각형의 최대 변의 길이는 max_side = min(N, M)

• 좌표 (r, c)가 어떤 정사각형의 좌측 상단 꼭짓점이고, 그 정사각형의 변의 길이가 i (1 <= i < max_side) 일 때,

• r + i, c + i가 인덱스 범위를 벗어나지 않고,
  네 꼭짓점의 값이 모두 같으면 (arr[r][c] == arr[r+i][c] == arr[r][c+i] == arr[r+i][c+i])

• 이때 만들 수 있는 정사각형의 크기는 (i+1) * (i+1)

• 가장 큰 정사각형의 크기를 저장하는 변수 ans의 값을 갱신해간다.

• N, M의 범위가 50보다 작은 자연수이므로 시간 복잡도는 O(50^3)으로 브루트포스로 해결 가능한 문제였다.