가장 큰 정사각형 찾기

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

프로그래머스

 

Level 2

 

DP 를 활용하여 현재 위치에서 만들 수 있는 가장 큰 정사각형을 구하는 문제

 

최초에는 모든 위치를 순차적으로 탐색해 최대 정사각형을 찾는 방법으로 구현했다. 

 

 

1. 현재 위치에서 길이가 N 인 정사각형을 만들 수 있는지 확인

2. N 은 1 -> Map 의 최대 길이 중 짧은 것(최대로 나올 수 있는 정사각형의 한 변의 길이) 으로 1의 총합으로 정사각형 판별

3. 정사각형이 안될 경우(내부에 1이 모자를 경우) Skip

 

위와 같은 방법으로 구현할 경우 정확성 테스트는 통과 가능하지만 효율성 테스트를 통과하지 못한다. 

결국 이리저리 고민하며 여러 방법으로 약간의 시간을 단축 해봤지만 효율성 테스트는 통과하지 못해 

공식 해설의 아이디어를 보고 DP 로 풀 수 있다는 것을 깨달았다. 아니 이걸 30분만에 떠올리고 구현할 수 있는건가

 

공식 해설에서 나온 아이디어를 토대로 나온 풀이는 다음과 같다. 

 

 

풀이의 핵심은 0이 아닌 모든 칸은 해당 위치에서 만들 수 있는 가장 큰 사각형의 한 변의 길이를 나타낸 다는 것.

즉, 위의 예시처럼 하얀색 1을 기준으로 좌/상/대각선의 값을 보고 그 중 가장 작은 사각형을 선택하여

현재 자신의 위치 만큼 작은 사각형의 우 하단이 증가하므로 다음과 같이 값을 갱신할 수 있다. 

 

 

이런 방법으로 행렬의 좌측 최상단에서 우측 최하단으로 완전 탐색을 하게 될 경우 행렬의 모든 1은 값이 갱신되며

(길이가 1인 정사각형이 있을 수도 있다)

최종적으로 0이 아닌 모든 값들 중 가장 큰 값을 찾으면 되는 것이다.

 

단, 반드시 현재 위치 (r, c) 에서 (r-1, c), (r, c-1), (r-1, c-1) 을 봐야하기 때문에

(r, 0), (0, c) 원소들은 인덱스 이탈 에러가 발생하므로 이를 방지하기 위해

기존 Map 에서 빈공간을 r, c 둘 다 1만큼 증가시켜 줌으로써 모든 원소를 정상적으로 탐색할 수 있다.

(빈 공간이 1씩 증가한다고 해서 Map 안의 최대 정사각형을 구하는 것에 영향을 끼치지 않는다)

 

public class Solution { //가장 큰 정사각형 찾기
    public int solution(int[][] board) {
        int[][] map = new int[board.length+1][board[0].length+1];
        for(int idxRow = 0; idxRow < board.length; idxRow++){ //빈 공간을 1만큼만 증가 시킨 커스텀 행렬
            for(int idxCol = 0; idxCol < board[0].length; idxCol++){
                map[idxRow+1][idxCol+1] = board[idxRow][idxCol];
            }
        }
        int answer = 0; //최대값
        for(int idxRow = 1; idxRow < map.length; idxRow++){
            for(int idxCol = 1; idxCol < map[0].length; idxCol++){ //증가한 행렬을 1,1 부터 maxRow,maxCol 까지 탐색
                if(map[idxRow][idxCol] > 0){ //빈 공간이 아닌 곳을 발견 시
                    int leftVal = map[idxRow][idxCol-1];
                    int topVal = map[idxRow-1][idxCol];
                    int diagonalVal = map[idxRow-1][idxCol-1];
                    map[idxRow][idxCol] = Math.min(diagonalVal, Math.min(leftVal, topVal))+1;
                    //현재 위치에서 정사각형의 가로, 세로 중 더 짧은 것을 선택
                    //선택된 가로 혹은 세로와 대각선 값을 비교하여 더 짧은 것을 선택
                    //만들 수 있는 최소의 정사각형의 한 변의 길이가 현재 위치인 우하단으로 1 증가
                    answer = Math.max(map[idxRow][idxCol], answer); //최대값 갱신
                }
            }
        }

        return answer;
    }
}