[Python] 1051 - 숫자 정사각형 (실버4)

1. 문제 설명

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

1051번: 숫자 정사각형

 

---

2. 아이디어

brute-force(전탐색)으로 해결했었다.

행과 열을 모두 옮겨다니면서 가로와 세로 중에 더 짧은 쪽을 기준(정사각형을 찾아야 하니까)으로

현재 지점(vertex)과 나머지 꼭짓점의 값이 같은 지점을 찾고, 현재 좌표에서 찾은 최대 넓이를

square 리스트에 저장시켜 둔다.

만약 값이 있다고 하더라도 현재 위치에서 찾은 더 큰 값이 있다면 if문에 걸리지 않는다.

 

그렇게 완성된 square 리스트에서 map함수를 이용해 각 열에서 최대값을 찾고

또 한 번 일차원 배열에서 최대값을 꺼내주면 해결되는 문제이다.

 

---

3. 코드

def solution():
    n, m = map(int, input().split())
    board = [list(map(int, input())) for _ in range(n)]
    square = [[1]*m for _ in range(n)]

    for row in range(n):
        for col in range(m):
            vertex = board[row][col]
            idx = min(n - row - 1, m - col - 1)
            while idx > 0:
                if board[row][col + idx] == vertex and board[row + idx][col] == vertex \
                    and board[row + idx][col + idx] == vertex and square[row][col] < (idx + 1) ** 2:
                    square[row][col] = (idx + 1) ** 2
                idx -= 1
    print(max(map(max, square)))
    
solution()