2학년 2학기 알고리즘 과제_3주차(백준_1051번:숫자 정사각형)

1051번: 숫자 정사각형

 

 

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

 

 

📌 내풀이 및 생각

 

N X M 크기의 직사각형이 있다고 했을 때, 그 중에서 가장 크게 만들 수 있는 정사각형의 네 개의 꼭짓점에 위치한 숫자가 같으면 해당 크기를 출력하면 되므로 정사각형을 가장 크게 만들 수 있는 크기를 출력하는 것이 해당 문제의 핵심이다.

 

해당 문제를 풀기위한 아이디어를 얻기위해 내용을 찾아봤다.

일단 해당 문제는 모든 경우를 다 해보면 되는데,  N과 M 중 더 작은 값을 Max_len이라고 하면, 한 변의 길이가 1인 정사각형부터 한 변의 길이가 Max_len인 정사각형까지 변의 길이를 1씩 증가시켜 가며 정사각형을 찾아주면 된다고한다.

 

정사각형의 네 꼭지점의 합이 가장 큰 정사각형을 찾아야 하는데 일단 왼쪽 위 꼭짓점을 기준으로 사각형을 만들고,

왼쪽 위 꼭짓점을 a, 왼쪽 아래 꼭짓점을 b, 오른쪽 위 꼭짓점을 c, 오른쪽 아래 꼭짓점을 d라고 하고, a = b = c = d이면 문제에서 구하라고 하는 조건을 만족하므로 해당 변의 길이(len)를 ans에 저장하도록한다.

 

 

📌 코드 분석

 

N, M = map(int,input().split())
A = [[] for _ in range(N)]

for i in range(N):
    A[i] = list(map(int,input()))

ans = []

if N >= M:
    size = M
else:
    size = N

i = 0
j = 0

#A는 A[11][10]
while size > 0:
    
    if A[i][j] == A[i+size-1][j] == A[i][j+size-1] == A[i+size-1][j+size-1]:
        ans.append(size**2)
    
    j += 1
    
    if j+size-1 >= M:
        j = 0
        i += 1
        
    if i+size-1 >= N:
        size -= 1
        i = 0
        j = 0
        
print(max(ans))

 

 

• 일단 주어진 직사각형 내 숫자들을 담을 수 있도록 하기위해 2차원 리스트에 입력받을 수 있는 A를 만든다.
• 이후, N, M 중에서 크기를 결정하는데, 사각형의 두 변 중 더 짧은 것이 최대크기인 maximum인 크기가 된다.
• 그 다음, 크기가 0이 될 때까지 반복을 해주면서 사이즈의 네 꼭짓점의 좌표 값이 같은 지 비교한다.
• 정사각형의 가로/세로 값이 주어진 직사각형의 크기보다 커지면 행의 값을 늘리고 열의 값은 초기화하도록 한다.
• 등호 쓴 이유는 배열에서는 크기 -1 까지가 최대값이기 때문이다.
• 행의 값이 주어진 직사각형의 세로 값보다 커지면 해당 사이즈에서는 더이상 경우가 없다는 의미이므로 사이즈를 줄여준다.
• 해당 조건을 만족하는 사이즈를 ans 배열에 계속 추가를 한 다음, 결과는 최댓값만을 출력하도록 한다.

 

 

📌 느낀점

 

 

해당 문제는 부루트 포스 알고리즘으로 분류하기도 하는 것 같다. 일단 해당문제를 접근할 때 , 그림을 그려봤더니 어떤식으로 문제를 구성했는지는 의미가 와닿았지만, 문제를 막상 풀려고 하니 알고리즘이 잘 그려지지는 않았다.

그래서 해당 문제풀이를 찾아보고 공부해봤는데, 내가 놓친 부분들이 보였고, 여러가지 풀이들을 찾아보았다.

단순히 한가지 풀이가 아니고 다양한 아이디어들을 보면서, 문제를 푸는 사고를 넓히는 것도 좋은 방법이라는 생각이 들었다. 

조금만 더 생각을 알고리즘으로 풀어낼 수 있는 공부가 필요할 것 같다.

 

 

[참고 자료]

[python] 백준 1051번 - 숫자 정사각형

[python] 백준 1051번 - 숫자 정사각형