백준 1051 숫자 정사각형

숫자 정사각형

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

• 기본적으로는 브루트포스를 이용하여 모든 경우의 수를 탐색하려 함.
• 이미 찾은 정사각형이 있다면, 그것보다 작은 경우들은 탐색하지 않음.

✔ 코드

import sys

def solution(arr):
    max_line_len = 0

    for i in range(len(arr)):
        for j in range(len(arr[0])):
            for length in range(max_line_len,50):
                ru = [i, j+length]
                ld = [i+length, j]
                rd = [i+length, j+length]

                if ru[1] < M and ld[0] < N and rd[0] < N and rd[1] < M:

                    num = arr[i][j]
                    if arr[ru[0]][ru[1]] == num and arr[ld[0]][ld[1]] == num and arr[rd[0]][rd[1]] == num:
                        # print([i,j], ru, ld, rd)
                        max_line_len = length
                else:
                    break

    return max_line_len
                

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    arr = []
    for _ in range(N):
        arr.append(list(map(int, list(sys.stdin.readline().rstrip()))))
    
    # for line in arr:
    #     print(line)

    ret = solution(arr)
    print(pow(ret+1,2))

☝ 팁

• 시간이 충분하여 모든 경우를 탐색할 수도 있을 것 같다.
  하지만 최대값을 구하는 문제의 경우, 현재 찾은 값보다 작은 경우는 탐색하지 않음으로써 탐색 횟수를 줄일 수 있다.