[백준] 1051번 : 숫자 정사각형

1051번: 숫자 정사각형

해당문제는 완전탐색 문제로 특정 좌표에서 정사각형을 그릴수 있는 크기를 구한뒤 후보를 정한뒤 각각의 후보에서 꼭지점의 수가 같은지 확인합니다.

1. 특정좌표에서 정사각형의 크기를 구하는 로직
   1. 크기 4의 정사각형 탐지법, 특정좌표에서 + (1, 1)의 값이 범위 안에 있는지 확인한다.
   2. 크기 9의 정사각형 탐지법, 특정좌표에서 + (2,2)의 값이 범위 안에 있는지 확인한다.
   3. N, M이 주어졌을때 정사각형의 크기는 반드시 N, M이랑 작거나 같다.
2. 꼭지점의 수가 같은지 확인법
   1. 크기 4의 정사각형 탐지법, 특정좌표에서 자기자신과 (1,1), (0,1), (1,0)가 같다면 꼭지점이 같다.
   2. 크기 9의 정사각형 탐지법, 특정좌표에서 자기자신과 (2,2), (0,2), (2,0)가 같다면 꼭지점이 같다.

N, M = map(int, input().split())
table = [[0 for _ in range(M)] for _ in range(N)]
move = ((0,1), (1,0), (1,1))
for i in range(N):
    temp = list(input())
    for j in range(len(temp)):
        table[i][j] = int(temp[j])

cnt = 0
for i in range(N):
    for j in range(M):
        # 정사각형임으로 더 작은 크기까지만 계산해본다.
        if M > N:
            MAXSIZE = M
        else:
            MAXSIZE = N

        for s in range(MAXSIZE-1, -1, -1):
            temp = [False for _ in range(3)]
            for k in range(len(move)):
                ny = i + move[k][0] * s
                nx = j + move[k][1] * s

                if N > ny >= 0 and M > nx >= 0: # 정사각형 범위라면
                    if table[i][j] == table[ny][nx]: # 꼭지점이 같다면
                        temp[k] = True
                else:
                    break
            if all(temp): # 모든 꼭지점이 같다면
                cnt = max(cnt, (s+1)*(s+1))

print(cnt)