728x90
반응형
문제:
N*M 크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.
입력:
첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.
출력:
첫째 줄에 정답 정사각형의 크기를 출력한다.
풀이방법:
N과 M의 크기가 50보다 작기 때문에 브루트 포스로 전부 탐색을 해도 된다. 1x1의 정사각형은 반드시 존재하기 때문에 넘어가고 가로, 세로 길이가 2인 정사각형부터 탐색을 시작한다. 한 변의 길이가 n이지만 좌표상의 차이는 n-1이 나게 된다. 따라서 이 점을 이용해서 꼭짓점의 값들이 같은지 탐색하고 같다면 answer를 변경하도록 한다.
만약 모두 탐색을 했는데 초기 answer이 변하지 않는다면 가장 큰 정사각형은 1x1이므로 1을 출력하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
n,m=map(int,input().split())
numbers=[]
for _ in range(n):
numbers.append(input())
dif=1
answer=0
while True:
for i in range(n-dif):
for j in range(m-dif):
if numbers[i][j]==numbers[i][j+dif]==numbers[i+dif][j]==numbers[i+dif][j+dif]:
answer=(dif+1)**2
dif+=1
if n-dif<=0 or m-dif<=0:
break
if answer==0:
print(1)
else:
print(answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/1051
1051번: 숫자 정사각형
N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.
www.acmicpc.net
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1718. 암호 (0) | 2020.04.09 |
|---|---|
| [BOJ]1302 베스트셀러 (0) | 2020.04.07 |
| [BOJ]2644. 촌수계산 (0) | 2020.03.24 |
| [BOJ]2352. 반도체 설계 (0) | 2020.03.19 |
| [BOJ]1748. 수 이어 쓰기 1 (0) | 2020.03.17 |