[알고리즘] 1051-숫자 정사각형 : Python

문제

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

 

입력

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

 

출력

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

 

[1051 - 숫자 정사각형] : https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

 

 

---

문제 풀이

얼마 전에 풀었던 DP문제랑 유사한 문제다.

 

[1915 - 가장 큰 정사각형] : https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

입력값
3 5
42101
22100
22101

 

1. 정사각형이 될 수 있는 가장 긴 변은 무엇인가?

3, 5중에 정사각형이 될 수 있는 가장 긴 변은 3이다. -> 답은 9보다 클 수 없다.

 

 

2. 정사각형 찾기

3 * 3 정사각형 후보부터 1 * 1 후보까지 차례대로 검사한다.

 

3. 찾은 최초의 정사각형이 정답

제일 큰 정사각형부터 검사하기 때문에 처음 정사각형이 나왔을 때 그 뒤로는 보지 않아도 된다.

 

코드

if __name__ == "__main__":
    import sys
    input = sys.stdin.readline
    row, col = map(int, input().split())
    datas = [list(input().rstrip()) for _ in range(row)]
    
    result = 0
    for k in range(min(row, col) - 1, -1, -1):
        for i in range(k, row):
            for j in range(k, col):
            	# 꼭짓점이 모두 같은지 확인
                if datas[i][j] == datas[i - k][j] == datas[i][j - k] == datas[i - k][j - k]:
                    print((k + 1) ** 2)
                    quit()