(프로그래머스) 가장 큰 정사각형 찾기

문제

https://programmers.co.kr/learn/courses/30/lessons/12905

풀이

처음에 특정 지점에서 모두 1로 구성된 정사각형 영역을 계속 구하자니, 반복적으로 탐색해야 한다는 점을 눈치채고 dp 문제라고 생각하였다.

방법은 간단하다.

1. 현재 위치의 원소가 1인지 확인한다. 0이면 정사각형 영역에 속할 조건 자체가 되지 않기 때문이다.

2. 현재 위치 기준 왼쪽, 왼쪽 대각선 위, 위를 조사한다.
   
   

   1	1
   1	1

   
   파란 글자를 현재 위치라고 했을 때, 빨간 글자로 된 원소들을 조사한다.
   이 원소들은 본인을 포함하여 왼쪽 위 방향으로 얼마나 큰 정사각형을 이루고 있는지를 나타내는 원소이며, 현재 위치의 원소 또한 그 역할을 하게 될 예정이다.

3. 그 중 가장 작은 원소 + 1로 현재 위치를 갱신한다.

코드

class Solution {
    public int solution(int[][] board) {
        int answer = 0;
        
        for (int i = 0; i < board.length; i++) {
            answer = Math.max(answer, board[i][0]);
        }
        
        for (int i = 0; i < board[0].length; i++) {
            answer = Math.max(answer, board[0][i]);   
        }
        
        for (int i = 1; i < board.length; i++) {
            for (int j = 1; j < board[0].length; j++) {
                if (board[i][j] == 0) {
                    continue;
                }
                
                board[i][j] = Math.min(Math.min(board[i - 1][j], board[i][j - 1]), board[i - 1][j - 1]) + 1; 
                answer = Math.max(answer, board[i][j]);
            }
        }
        
        return answer * answer;
    }
}

dp라고 막연하게 생각하고 끼워맞추려고 하지 말고, 적절한 이유와 반례를 충분히 생각하는 것이 중요한 것 같다.