[백준] 1051. 구현_숫자정사각형 - Python

문제

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

입력

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

출력

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

 

 

★ 시작하기 전에

막연했다. 도저히 알고리즘의 기초인 경우를 나누어 조건을 거는 방법이 생각나지 않았다.

도대체 어떤 분야의 문제인가 하고 보니까 브루트 포스... 처음 들어보는 단어였다. 찾아보니 완전탐색?이라 생각하면 되는 것일까?

결국 다 해보라는 거였다. 그래서 안보이는 거였다.

그래서 board의 한 원소마다 꺼내어 해당 조건을 걸 수 있는지 확인했다. 처음 시도는 깔끔하지 않아 다시 정리를 하며 풀이를 해 보았다.

1. 하나의 원소씩 다 확인해 볼 것.

2. 우측, 아랫쪽 끝에서는 어떻게 할 것인가? 아래 k 측 변의 길이를 나타내는 부분이 0이 되지 않도록 한다.

3. 이건 반례 검색을 통해 본 것이지만, 단 한 숫자만으로도 1이라는 넓이를 낼 수 있다.

이를 생각하고 풀어나가면 된다.

 

#브루트포스? 결국 완전탐색같은건가
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().strip())))
######################이상 입력 받아 board를 만들었다#########################
result = []
# 도저히 경우의 수를 나눠서 생각할 수가 없었다.
# 초기 방법 : board에서 한 원소씩 꺼내어 n, m중 작은 값만큼 확장하여 점점 작게 만들며 꼭지점 값 비교
# 아래 방법 : 시작점(all)으로부터 그 시작점이 가질 수 있는 최대 변의 길이를 찾아보았다.
# 가로로 펼칠 수 있는 최대, 세로로 펼칠 수 있는 최대 중 작은 값을 기준으로 잡는다.
# i, j 인덱스를 활용하기 때문에 쉽게 꼭지점을 비교할 수 있었다.
for i in range(n):
    for j in range(m):
        width = m-1 - j
        height = n-1 - i
        std = min(width, height)
        for k in range(1,std+1):
            if board[i][j] == board[i+k][j] and board[i][j] == board[i+k][j+k] and board[i][j] == board[i][j+k] and k!=0:
                result.append((k+1)**2)
if result:
    print(max(result))
else:
    print(1)

식은 짧지만 생각은 꽤나 했던 애증의 문제... 문제를 보고 완탐, 브루트포스인지 어떻게 알지.....