[Python] Baekjoon1051: 숫자 정사각형

숫자 정사각형

2 초

128 MB

12802

4824

4081

38.269%

문제

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

입력

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

출력

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

풀이

전형적인 브루트 포스적인 문제라고 생각했습니다. 단계적인 생각으로 풀어나갔습니다.

1) 입력값을 리스트나 2차원 리스트에 집어넣기

2) 리스트 내부의 값들을 순서대로 탐색하며 함수 실행

함수 작동 원리

3) 현재 탐색하는 값을 1이라고 가정합니다

4) 같은 행에서 탐색[가로]:  현재 index보다 큰 값부터 탐색을 시작해 1과 같은 값을 발견하면 5)번으로 넘어갑니다

5) 같은 열에서 탐색[세로]: 처음1과 나중1의 위치를 빼서 사각형의 한 변의 길이(length)를 구하고 그 만큼 더해 세로줄에서 찾습니다

6) num이 있는 곳에서 행+ 사각형의 길이만큼 더한 뒤 그 위치로 찾아가 1과 같은 숫자인지 확인합니다. 만약 같다면 7로 넘어갑니다

7) 여기까지 도달했다면 기준점 1과 가로에 하나 1 세로에 하나 1을 구한 상태입니다. 대각선의 좌표의 값도 1인지 확인합니다

8) 대각선의 값도 1이라면 한 변의 길이를 제곱해 정사각형의 넓이를 구하고 최대값을 갱신합니다.

N, M = map(int, input().split())
lst = []  # 빈 리스트

# [조건]: N, M은 자연수 = 정답의 최소값은 1, 사각형은 정사각형
MAX = 1

# 사각형이 맞는지 찾아주는 함수
def find_square(number, row, col):
    for colF in range(col, M):  # 같은 행부터 조사( 열을 바꿔야함 )
        if lst[row][colF] == number:
            length = colF - col # 실제길이는 + 1 을 해야하지만 계산을 위해 보류
            if(row + length < N and lst[row+length][col] == num and lst[row+length][col+length]==number):
                area = (length+1) ** 2
                global MAX
                if area > MAX:
                    MAX = area

# 2차원 배열? NO! 문자열!
for i in range(N):
    lst.append(input())

# 브루트 포스: 전체 탐색
# 한 점을 정했을 때 내 앞은 탐색하지 않고 내 뒤만 탐색한다
for i in range(N):
    for j in range(M):
        num = lst[i][j]  # 문자열 저장이지만 형변환? 필요X
        find_square(num, i, j)
        
# 출력
print(MAX)