[BOJ][Python]1051번 풀이

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

1051번: 숫자 정사각형

개인적으로 해당 문제의 설명이 너무 별로라고 생각해서 제 나름대로 이해가 쉽도록 좀 고쳐보겠습니다.

 

문제:

1x1 크기의 칸이 세로N개, 가로M개의 형태로 나열되어 하나의 직사각형을 이루고 있으며, 각 칸에는 한 자리 숫자가 적혀 있다. 어떤 정사각형의 꼭짓점이 NxM 직사각형 내부의 숫자가 적혀있는 칸 위에 위치한다고 가정할 때, 꼭짓점이 위치한 칸에 쓰여 있는 수가 모두 같고 넓이가 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

 

입력:

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 직사각형 내부의 칸에 적힌 한 자리 숫자가 주어진다. 각 숫자는 공백없이 붙여서 주어진다.

 

사실 별 거 아니기도 하고 문제를 입력과 비교하면서 읽으면 무슨 소린지 이해가 가긴 합니다만, 개인적으로 해당 문제를 읽으면서 출제자 자신을 제외한 사람들에게 배려가 없다는 생각이 들었기 때문에 고치지 않을 수 없었습니다. 문제 자체는 안어려운데 출제자가 무슨 말을 하는지를 이해해야 하는 문제는 정말 오랜만인 것 같네요.

 

import sys
ssr = sys.stdin.readline

n,m = map(int, ssr().split())
r = [list(ssr().rstrip()) for _ in range(n)]
s = n if n<m else m
ans = 1
for i in range(1,s):
    for j in range(n-i):
        for k in range(m-i):
            check = int(r[j][k])
            if int(r[j+i][k]) == check and int(r[j][k+i]) == check and int(r[j+i][k+i]) == check:
                ans = (i+1)**2
print(ans)

문제는 그냥 4개의 값을 다 탐색하기만 하면 되는 간단한 브루트포스 문제입니다. n과 m은 각각 50까지이니 최대 2500개의 숫자가 2차원 리스트로 이뤄질거구요. 정사각형의 크기는 i의 자승이기 때문에 실제로는 2500번을 다 도는 경우는 1번밖에 없어서 제한 2초면 시간은 충분합니다.

 

문제 접근 방법은 당연히 브루트 포스 알고리즘을 사용합니다. 정사각형이 주어진 조건이기 때문에 index 에러를 피하기 위해서 i의 최대 사이즈를 n이나 m 중 작은 것으로 선택합니다. 그렇게 하고 i의 크기에 따라 2차원 리스트를 탐색해야하기 때문에 3중 반복문을 구성해줍니다. 다만 아예 불가능한 경우의 출력이 1이기 때문에 ans는 1로 초기화 해주었습니다. 답이 있다면 바꿔주면 되구요.