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

 

 

N, M = map(int, input().split())
arr= [[0 for _ in range(M)] for _ in range(N)] # 2차원 배열 
for i in range(N):
    temp = list(map(int, input().strip()))
    for j in range(M):
        arr[i][j] = temp[j]


final = 1
max_len = min(N, M) # 정사각형의 최대 길이 (둘 중 더 짧은 것)
for length in range(1, max_len):
    for i in range(N-length):
        for j in range(M-length):
            a = arr[i][j]
            b = arr[i + length][j]
            c = arr[i][j + length]
            d = arr[i + length][j + length]
            if (a==b==c==d):
                final = length + 1
    
print(final**2)

 

 

현재 숫자들의 목록을 띄어쓰기 없이 배열로 행마다 받고 있기 때문에, 미리 N*M 크기의 arr 2차원 배열을 만들어 놓고 여기에 input().strip()과 이중 반복문을 이용하여 준비해뒀던 arr 배열에 숫자를 하나씩 삽입한다.

 

이렇게 배열 세팅이 완료되었으면 이제 정사각형의 각 꼭짓점을 뽑아서 모든 꼭짓점이 일치하는지 여부를 판단해야 한다.

아이디어로는 배열에서 N*M 크기의 영역을 스캔해나가면서, 네 꼭짓점의 값이 동일한 가장 큰 정사각형을 찾는 것이다.

이를 위해 반복문에서 정사각형의 변의 길이를 점차 늘려나가며 가능한 최대 크기를 탐색한다.

 

위 코드에서 final이라는 변수는 최소 길이 1의 정사각형을 초깃값으로 둔다. (기본값이 1x1)

이 1x1 크기의 정사각형부터 탐색해나가는 셈임

또한 N과 M 중에 작은 값이 탐색하는 정사각형의 최대 변의 길이가 되므로 min()을 사용하여 이 중 작은 값을 정사각형의 max_len으로 설정함

 

탐색 과정에서는 삼중 for 반복문을 사용

1. 첫 번째 for문 : 변의 길이가 1인 경우는 이미 처리된 상태이므로 2 이상부터 max_len-1 길이까지 증가시키며 검사

2. 두 번째 for문 : 정사각형의 좌상단 모서리의 행 위치를 지정

배열에서 정사각형의 변의 길이가 length일 때, 왼쪽 상단 모서리의 행 인덱스 i는 N-length까지만 가능해야 정사각형이 배열을 벗어나지 않음!

3. 세 번째 for문 : 정사각형의 좌상단 모서리의 열 위치를 지정

행과 마찬가지로 j는 M-length까지만 가능해야 배열을 벗어나지 않음

 

그리고 a,b,c,d를 각각 왼쪽 상단, 왼쪽 하단, 우측 상단, 우측 하단의 좌표로 설정하고, 앞서 있었던 반복문의 i와 j 값에 따가 인덱스를 이에 맞게 지정해준다.

탐색 도중에 네 꼭짓점이 모두 같은 정사각형이 나왔다면, 현재 정사각형의 변 길이 length+1로 final을 우선 업데이트 해주고 이것보다 큰 정사각형이 나올 수도 있으므로 남은 반복을 이어간다.

(변의 길이가 0부터 시작하기 때문에 실제 길이를 표현하기 위해 +1을 넣은 것임)

 

최종적으로 정사각형의 넓이를 출력해야 하므로 한 변의 길이인 final에 제곱을 한 값을 출력해준다!