[백준 1051] 숫자 정사각형 - python (solved.ac - 실버 3)

https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

풀이

문제를 보았을때 알수있는 힌트

처음 문제를 보았을때 이해조차 못했다. 직사각형이 있는데 직사각형을 내가 그리는 건가 하면서 20분을 고민하고 있있다. 다시 문제를 보고 확인해보니 예제에 나와있는 직사각형의 모습으로 아래에 숫자로 표현이 되어있는 것이였다.

그 중에 4개의 꼭지점이 같은 최대로 큰 정사각형을 찾는 문제였다.

예제 1번에서는 1로 각 꼭지점으로 두면 3X3으로 최대로 큰 정사각형을 만들수있다. 

그러면 어떻게 풀면 될까?

먼저 2차 배열 문제이기에 리스트에 2차 배열이 담길수있게 작업을 진행했다.

 

2차 배열을 담고나서 최대로 나올수있는 정사각형을 찾고 천천히 정사각형의 사이즈를 줄여나가는 형식으로 진행하였다.

예제 1번의 경우 3X5의 직사각형이므로 3X3이 제일 큰 정사각형이다.

이를 min(3,5)를 하여 최대로 큰 정사각형을 찾았다.

 

이후 천천히 줄어들수있게 반복문을 줄어들수있게 세팅하였다.

줄어드는 반복문안에 x,y축으로 움직일수있는 수를 세팅하였다.

예제를 보면 3X3의 경우 x축으로는 2번 움직일수있고, y축으로는 0번 움직일수있다.

이를 간단하게 계산해보면 최대길이는 5에서 정사각형의 3을 뺀 2가 되고, 나머지 직사각형 길이인 3과 정사각형의 3을 뺀 0번이 되는 것을 알수있다.

이때 결과를 찾지 못했다면 2X2의 정사각형으로 돌것이며 이때는 x축은 5-2=3번, y축은 3-2=1번을 움직일수있다.

이렇게 2X2까지 돌리고 찾지 못했다면

결과는 무조건 1이 나오게 코드를 짜면 끝이 난다.

 

내가 짠 코드에서는 for문을 자주사용하여 break를 나가기위해 breaker인 bool식을 사용하였다.

 

import sys

input= sys.stdin.readline

n,m= list(map(int,input().split()))
list_n=[]

for i in range(n):
    list_n.append(list(map(int,input().strip())))

breaker=False
result=1
max_n=min(n,m)-1
for i in range(max_n,0,-1):
    for j in range(n-i):
        for k in range(m-i):
            if list_n[j][k]==list_n[j+i][k]==list_n[j][k+i]==list_n[j+i][k+i]:
                result=(i+1)*(i+1)
                breaker=True
                break
        if breaker==True:
            break
    if breaker==True:
        break
    
print(result)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1051.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리