[ 알고리즘 ] 코딩 - Programmers - 가장 큰 정사각형 찾기.java

문제 링크

---

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

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

---

* Programmers - level 2 - (자바)가장 큰 정사각형 찾기 - DP

예시

* 처음에는 for문을 이용해서 전체 순회해서 가장 큰 정사각형을 찾는 방식으로 하려고 했다.

* 하지만.. 보통일이 아니었고, 효율성이 정말이지 바닥을 쳤다.

* 결국 찾아보니 세상에나 이 문제는 DP 문제였던 것이다!!!

---

< logic >

1. 기준점에서 왼쪽 / 위쪽 / 왼쪽 대각선 위 의 현재 숫자를 본다

2. 0이 아니라면 3방향 중 최소인 숫자 + 1을 하고 저장해준다.

3. 저장 한 숫자가 가장 큰 정사각형의 한 변의 크기가 된다!

예시 그림

3 방향 수 + 1 중 최소인 값으로 갱신 

최대 길이를 찾을 때까지 갱신 한 모습

갱신과 동시에 최대인 값도 갱신한다.

모든 과정이 끝나고 나온 최대값이 정답!

---

class Solution
{
    public int solution(int [][]board)
    {
      int answer = 0;
      int height = board.length; // 세로길이
      int width = board[0].length; // 가로길이
      int[][] map = new int[height + 1][width + 1]; // 원본에 0 패딩할 배열
 
 	// 배열 복사
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            map[i + 1][j + 1] = board[i][j];
        }
    }
 
    for (int i = 1; i <= height; i++) {
        for (int j = 1; j <= width; j++) {
            if (map[i][j] != 0) { // 0이 아닌 경우에 한해서, 최소를 찾는다
                map[i][j] = Math.min(Math.min(map[i - 1][j], map[i][j - 1]), map[i - 1][j - 1]) + 1;
                answer = Math.max(answer, map[i][j]); // 최대값 갱신
            }
        }
    }
 
    return answer * answer;
    }
}