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

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

코딩테스트 연습 - 가장 큰 정사각형 찾기

2021-08-02

---

class Solution {
    public int solution(int [][]board) {
        int answer = 1;
        boolean flag = false;
         for (int[] ints : board) {
            for (int anInt : ints) {
                if (anInt == 1) {
                    flag = true;
                    break;
                }
            }
        }
        if(!flag)return 0;
        for(int i = 1; i < board.length; i++) {
            for(int j = 1; j < board[i].length; j++) {
                if(board[i][j] == 1) {
                    board[i][j] = Math.min(board[i-1][j-1], Math.min(board[i-1][j], board[i][j-1])) + 1;
                    answer = Math.max(answer, board[i][j]);
                }
            }
        }
 
        return answer*answer;
    }
}

#문제풀이

1. 1이 하나도 없는 경우를 체크한다. (테스트 8번?)

 

2. 1이 있는 경우에는 (1, 1)부터 체크한다.

 

3. 현재의 board[x][y] 값이 1인 경우, 왼쪽, 왼쪽 대각선 위, 위 3군데를 체크한다.

이 때, 체크하는 3군데의 값 중 가장 작은 값 + 1을 board[x][y]의 새로운 값으로 대체한다. 

가장 작은 값으로 하는 이유는 정사각형을 만들 수 있는지에 대한 최솟값을 체크하기 위함이다.

 

예를들어, 0, 1, 1로는 정사각형을 만들 수 없다. 그래서 최솟값(0)+ 자기 자신(1) 1 로 갱신을 하면 된다.

예를 들어, 1, 1, 1로는 변의 길이가 최대 2인 정사각형을 만들 수 있다.  그래서 최솟값(1) + 자기 자신(1) 2로 갱신을 하면 된다.

예를 들어, 1, 1, 2로는 변의 길이가 최대 2인 정사각형을 만들 수 있다. 그래서 최솟값(1) + 자기 자신(1) 2로 갱신된다.

이를 반복하면, 맨 마지막에 이러한 결과를 얻을 수 있다.