문제:

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

 

'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

+ Recent posts