![react](https://tistory1.daumcdn.net/tistory/4365896/skin/images/react-logo.png)
즐겁게, 코드
BOJ 1051번 - 숫자 정사각형 본문
1051번: 숫자 정사각형
N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는
www.acmicpc.net
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
(0, 0)부터 시작해 2차원 배열의 각 인덱스를 순회하며 가능한 정사각형을 구한 뒤, 꼭지점의 값들이 모두 같은지 여부를 체크하면 됩니다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
구현 아이디어가 어려운 편은 아니지만, 정사각형의 인덱스가 원래 배열을 넘어서지 않게 하는데 애를 꽤나 먹었었네요.
(결국 이 부분은 조건문을 별도로 두어 처리했습니다.)
또, 명시되지 않은 부분이지만 입력으로 1 * 1 배열이 주어지면 0이 아닌 1을 출력해야 합니다.
[정답 코드 - Python]
N, M = map(int, input().split())
square = []
max_size = 1
for _ in range(N):
square.append(list(map(int, input())))
def findSquare(row, col):
size = 0
for i in range(1, min(N, M) - min(row, col)):
if row + i >= N or col + i >= M: continue
if square[row][col] == square[row + i][col] == square[row][
col + i] == square[row + i][col + i]:
size = i + 1
return size * size
for row in range(N - 1):
for col in range(M - 1):
size = findSquare(row, col)
if max_size <= size:
max_size = size
print(max_size)
+ 여담이지만 제 기준으로는 깔끔하게 구현한 것 같아 뿌듯했던 문제였습니다.
반응형
'💯 알고리즘 > 백준 온라인 저지' 카테고리의 다른 글
BOJ 2583번 - 영역 구하기 (0) | 2021.04.29 |
---|---|
BOJ 2606번 - 바이러스 (0) | 2021.04.27 |
BOJ 1895번 - 필터 (0) | 2021.04.24 |
BOJ 20055번 - 컨베이어 벨트 위의 로봇 (0) | 2021.04.17 |
BOJ 7576번 - 토마토 (1) | 2021.04.14 |
소소한 팁 : 광고를 눌러주시면, 제가 뮤지컬을 마음껏 보러다닐 수 있어요!
와!! 바로 눌러야겠네요! 😆