[프로그래머스]가장 큰 정사각형 찾기

[78] 가장 큰 정사각형 찾기

책 구매하기

문제 정보

• 분류: 동적 계획법
• 정답률: 44%
• 권장 시간 복잡도: O(R * C)
• 핵심 키워드: 정사각형 DP, 왼쪽/위/대각선, 최대 한 변, 점화식
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12905

문제를 읽을 때 체크할 포인트

현재 칸이 1일 때만 정사각형을 키울 수 있고, 그 크기는 왼쪽·위·왼쪽위 대각선 셋 중 최솟값에 1을 더한 값으로 정해진다.

여기서는 정답 자체보다 '상태를 어떻게 잡을 것인가'가 먼저다. 현재 상태에서 다음 상태로 가는 비용만 잘 세우면, 긴 설명보다 점화식 하나가 더 강하다.

풀이 흐름

1. 첫 행, 첫 열은 그대로 시작한다.
2. 1인 칸마다 왼쪽/위/대각선 값의 최소에 1을 더한다.
3. 가장 큰 한 변 길이의 제곱을 반환한다.

구현할 때 놓치기 쉬운 부분

정사각형 여부는 현재 칸 하나만 보고 판단할 수 없다. 오른쪽, 아래, 대각선 값 중 최솟값에 1을 더하는 점화식을 써야 가장 큰 정사각형 한 변의 길이를 정확히 구할 수 있다.

파이썬 정답 코드

def solution(board):
  # 첫 행, 첫 열은 그대로 시작한다.
  rows, cols = len(board), len(board[0])
  answer = 0

  # 1인 칸마다 왼쪽/위/대각선 값의 최소에 1을 더한다.
  for r in range(rows):
    # 가장 큰 한 변 길이의 제곱을 반환한다.
    for c in range(cols):
      if board[r][c] == 1 and r > 0 and c > 0:
        board[r][c] = min(board[r - 1][c], board[r][c - 1], board[r - 1][c - 1]) + 1
      answer = max(answer, board[r][c])

  return answer * answer

시간 복잡도

R은 행 수, C는 열 수이다.

격자 전체 칸 수가 R×C개이고, BFS나 DP가 각 칸을 많아야 한두 번씩만 처리한다. 그래서 행 수와 열 수의 곱이 그대로 전체 비용이 된다.

따라서 시간 복잡도는 O(R * C)이다.