백준 1051번: 숫자 정사각형 (Python)

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

1051번: 숫자 정사각형

---

Level: Silver III

Solved By: Brute-Force

 

1. 구할 수 있는 제일 큰 정사각형의 사이즈를 알아냅니다. -> \(size = min(n,m)\)
2. 이 사이즈부터 시작하여 사이즈에 해당하며, 원소 값이 모두 동일한 정사각형이 있는지 Brute-Force 하게 탐색합니다.
3. 정사각형이 있을 때까지 2번 과정을 사이즈를 한 칸씩 줄여가면서 탐색합니다.
4. 만약에 있다고 판단이 되면, 거기서 반복문을 종료하며 해당 사이즈에 대한 면적 값을 구하면서 프로그램을 종료시킵니다.

이번 문제에서 알아가야 했던 점은 '파이썬에서는 공백 없이 주어진 수열의 입력을 어떻게 하나씩 처리할 것인가?'였습니다.

input: 12345, output: [1, 2, 3, 4, 5]

기존에는 map(int, input().split())을 통해서 split에 들어가는 argument가 무엇인지를 통해 구분자를 지정하여 입력을 받을 수 있었는데 공백이 없는 수열은 구분자를 ''라고 지정을 하면, ValueError: empty separator라는 에러가 발생합니다.

 

이에 대한 답으로는 map(int, input())을 사용하면 풀립니다. 이유를 알아봅시다.

 

map함수의 파라미터는 map(function, iterable)로 나뉩니다. 이때 iterable이란 반복 가능한 Data Structure로 리스트, 문자열 등 쉽게 말해 인덱싱이 가능한 객체들을 뜻합니다.

이때 input().split()의 type은 list로 나오고, input()의 type은 string으로 나옵니다. 여기서 가능했던 이유를 알 수 있는데 input()을 통해 string으로 받았기 때문에 문자열의 각 문자 원소에 접근을 하여 int function을 적용함으로써 공백 없이 주어진 수열의 입력을 의도한 대로 처리할 수 있는 것입니다.

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

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

def findlen(b, length):
    for i in range(0, n-length+1):
        for j in range(0, m-length+1):
            if b[i][j] == b[i+length-1][j] and b[i+length-1][j] == b[i][j+length-1] and b[i][j+length-1] == b[i+length-1][j+length-1]:
                return True
    
    return False

def main():
    size = min(n, m)
    answer = 1
    
    for value in range(size, 0, -1):
        if findlen(board, value) == True:
            answer = value * value
            break
    
    print(answer)
    
main()