백준 #1051 - 숫자 정사각형

 

 

문제

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

입력

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

출력

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

예제 입력 1

3 5
42101
22100
22101

예제 출력 1

9

예제 입력 2

2 2
12
34

예제 출력 2

1

예제 입력 3

2 4
1255
3455

예제 출력 3

4

예제 입력 4

1 10
1234567890

예제 출력 4

1

예제 입력 5

11 10
9785409507
2055103694
0861396761
3073207669
1233049493
2300248968
9769239548
7984130001
1670020095
8894239889
4053971072

예제 출력 5

49

 

 

---

 

우선, n * m 크기의 직사각형을 표현하기 위해 rec이라는 이차원 배열을 만들었다.

그 후, 직사각형의 숫자를 입력받아 rec 배열에 저장했다.

 

그 후, 왼쪽 위 첫번째 점부터 대각선 아래로 순회하며 검사를 진행했다.

 

왼쪽 위 모서리를 기준으로, 오른쪽 아래 모서리를 탐색하며

1) 해당 두 모서리가 정사각형을 만드는지

2) 4개의 모서리가 모두 같은 숫자를 나타내는지

 

위 두 요구사항을 충족하는 정사각형의 모서리를 구하고, max 함수를 통해 가장 넓은 값을 구했다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

rec = [[0] * (m) for _ in range(n)]  # 직사각형 정보 저장할 이차원 배열

for i in range(n):  # 이차원 배열에 직사각형 정보 저장하기
    nums = input()
    for j in range(m):
        rec[i][j] = nums[j]

space = 1  # 조건에 맞는 정사각형이 없을 시, 넓이는 1이므로 초기값 1로 설정

for i in range(n):
    for j in range(m):  # 왼쪽 위 모서리
        left = rec[i][j]
        for k in range(i + 1, n):  
            for l in range(j + 1, m):  # 오른쪽 아래 모서리
                if (k - i) == (l - j) and rec[k][l] == left and rec[i][l] == left and rec[k][j] == left:
                # 정사각형인지, 그리고 4개의 모서리가 다 같은 숫자인지 검사하기
                    space = max(space, (k - i + 1)**2)  # 조건에 맞다면, 최댓값을 넓이로 저장

print(space)