[Python] 백준 풀기 1051 - 숫자 정사각형

파이썬 백준 1051번

실버 4

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

1051번: 숫자 정사각형

 

 

 

 

 

문제 보기

분류: 구현, 브루트포스 알고리즘

 

 

 

 

 

문제 풀기

모든 좌표에 대해 가능성을 탐색한다. 이때, 기준 좌표를 결정하여 그 좌표로부터 가로, 세로에 대해 같은 값이 있는지를 찾는다.

 

최소 넓이는 네 개의 같은 수가 존재하지 않은 하나의 수만 있을 경우이므로 1 로 초기화한다.

하나의 좌표를 기준으로 잡고 그 값을 저장하여 가로축에 대해서 같은 숫자가 있는지를 찾고 있다면 세로축의 동일한 거리에 있는 숫자가 기준 숫자와 같은지를 판별한다. 세로축에서 찾은 숫자도 같다면 그 가로에 있는 숫자도 비교하여 정사각형을 이루는지 확인한다.

정사각형이 이루어졌다면 그 넓이를 저장하되 기존에 저장된 초기값보다 큰 숫자인 경우에만 시행한다.

모든 가능성의 정사각형을 판별하고 저장된 최대 넓이를 출력한다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnFindSquare(n, m):
    max_area = 1; # 최소 넓이는 하나의 숫자로 이루어져 있기 때문에 초기값을 1 로 설정.
    
    for i in range(n):
        for j in range(m): # 모든 좌표를 탐색.
            vertex = rectangle_ls[i][j] # 하나의 좌표를 기준으로 잡아 그 숫자를 저장하고 시작.
            for k in range(j, m): # 기준을 잡은 좌표의 가로 방향 탐색.
                if k != j and vertex == rectangle_ls[i][k]: # 기준 좌표를 제외하고 같은 숫자가 나타났을때.
                    
                    if i + (k - j) <= n - 1 and vertex == rectangle_ls[i + (k - j)][j]: # 세로 방향 index 를 벗어나지 않는 범위에서 기준 숫자와 같은 좌표가 있을때.
                        if vertex == rectangle_ls[i + k - j][k]: # 세로 방향 탐색 후 그 가로 방향의 같은 숫자가 있는 좌표가 있을때.
                            
                            print(i, j)             ## TEST PRINT, POINT 1
                            print(i, k)             ## TEST PRINT, POINT 2
                            print(i + (k - j), j)     ## TEST PRINT, POINT 3
                            print(i + (k - j), k)     ## TEST PRINT, POINT 4
                            
                            area = (k - j + 1) ** 2 # 위의 if 조건을 모두 만족하면 정사각형. 그 넓이.
                            print(f'area: {area}')             ## TEST PRINT
                            
                            if max_area < area: # 최대값이 나타나면 그 값을 다시 저장.
                                max_area = area
    
    return max_area


if __name__ == "__main__":
    n, m = map(int, inputdata().split())
    
    rectangle_ls = [] # 2차원 좌표를 저장할 리스트 생성.
    
    for _ in range(n):
        rectangle_ls.append(list(map(int, inputdata().strip())))
    
    # print(rectangle_ls)             ## TEST PRINT
    
    result = fnFindSquare(n, m)
    print(result)



'''
3 5
42101
22100
22101

0 2
0 4
2 2
2 4
area: 9
1 0
1 1
2 0
2 1
area: 4

9
'''