Koala - 10기/코딩테스트 준비 스터디
[백준/Python] 1051번 : 숫자 정사각형 (완전 탐색)
쥬발이
2023. 3. 8. 23:37
1. 문제
1051번: 숫자 정사각형
N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행
www.acmicpc.net
2. 해결방법
- 완전 탐색을 이용했다 ! N,M은 50보다 작거나 같은 자연수이다. 그럼 N*M정사각형 좌표 하나씩을 다 탐색해봤자 25000~
완전 탐색을 하기엔 충분한 숫자라고 판단했다.
- 우선 사각형을 2중 리스트로 입력받는다.
- k(사각형 길이 탐색) 변수를 두고 i,j(사각형 좌표)에서 (i, j) , (i,j+k) , (i+k, j), (i+k, j+k)가 같은 k를 탐색한다.
- 가장 큰 k로 계속 side 갱신 !!
3. 코드
n,m = map(int,input().split())
square = [list(input()) for _ in range(n)]
side = 0
for k in range(min(n, m), 0, -1):
for i in range(n-k):
for j in range(m-k):
if square[i][j] == square[i][j+k] == square[i+k][j] == square[i+k][j+k]:
side = max(side,k+1)
if side !=0:
print((side)**2)
else:
print(1)아직 코드가 마무리까지 부드럽진 않은 것 같다! 계속 문제로 연습해야겠다 ..