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

문제

 

백준 1051번 숫자 정사각형

문제 링크 : https://www.acmicpc.net/problem/1051

 

 

문제 풀이

목적 : NxM 크기를 가진 숫자 배열이 있을 때, 정사각형의 네 꼭짓점의 수가 같을 경우, 가장 큰 정사각형의 넓이를 구하는 것

정사각형을 이룰 수 있는 가장 큰 변의 길이부터 변의 길이가 1이 될 때까지 1씩 줄여가며, 해당 길이의 정사각형이 있는지 여부를 확인한다. 가장 긴 변을 가진 정사각형을 찾는 것이므로, 그리디 알고리즘을 사용하여 변의 길이(side)를 내림차순으로 탐색하여 정사각형이 존재하면 즉시 중지한다.

위치를 탐색할 때에는 행의 인덱스 i와 열의 인덱스 j를 가진 왼쪽 위 점을 기준으로, side 만큼 떨어진 오른쪽 위, 왼쪽 아래, 오른쪽 아래 점을 인덱싱하여 탐색한다.

 

코드

import sys

input = sys.stdin.readline

n,m=map(int,input().split(' '))
board =[list(map(int,input().rstrip())) for _ in range(n)]

# 현 위치를 포함하기 때문에 구하고자 하는 변의 길이에서 1을 뺀 값을 side 변수로 사용한다.
side = min(n,m)-1
answer=0

# side가 음수일 경우 중지
while side>=0:
  # 왼쪽 위 위치 i, j를 탐색한다. 모든 점을 탐색하지 않는다.
  for i in range(0,n-side):
    for j in range(0,m-side):
      # 각각 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 위치의 값을 구한다.
      lu=board[i][j]
      ru=board[i][j+side]
      ll=board[i+side][j]
      rl=board[i+side][j+side]
      # 모두 일치한다면 answer에 값을 작성한다. 다른 정사각형이 발견되더라도 while문 안에서 같은 side를 가진 정사각형이므로 answer 값 자체는 변하지 않는다. 
      if lu==ru==rl==ll:
        answer=(side+1)**2
  # 정사각형이 발견되지 않으면 side에서 1을 뺀 후 다시 탐색
  if answer==0:
    side-=1색
  # 정사각형 발견 시 출력 후 중지
  else:
    print(answer)
    break