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

문제

• 1와 0로 채워진 표(board)가 있습니다.
  • 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다.
• 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
  • 예를 들어

• 가 있다면 가장 큰 정사각형은

• 가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

조건

• 표(board)는 2차원 배열로 주어집니다.
  • 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
  • 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
  • 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

입출력 예

 

입출력 예 설명

• 입출력 예 #1
  • 위의 예시와 같습니다.
• 입출력 예 #2
  • | 0 | 0 | 1 | 1 |
  • | 1 | 1 | 1 | 1 |
  • 로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

솔루션

• 결론부터 얘기하자면 \((i, j)\) 위치의 값 (정사각형 한 변의 길이가 된다) 을 왼쪽 \((i, j - 1)\), 위쪽\((i - 1, j)\), 대각선 위치 \((i - 1, j - 1)\) 값 중 최소값 + 1의 값으로 갱신하면서 진행한다.
  • 예시 그림을 통해 보자.

그림 1

• 위 그림에서 나올 수 있는 최대 정사각형의 한 변의 길이는 1이다.
  • 최소값이 0이기 때문이다.
  • 따라서 빨간 테두리로 표시된 곳 \((i, j)\) 의 값은 1로 갱신한다.
• 두 번째 예시 그림을 보자.

그림 2

• 초록 테두리로 표시된 위치 값은 화살표가 나오는 방향의 값들 중 최소값인 1에 + 1 = 2의 값으로 갱신한다.
  • 이런 식으로 진행하여 최종적으로 나오는 값들은 아래 그림과 같을 것이고, 최대 정사각형 한 변의 길이는 빨간 테두리로 표시된 값인 3, 넓이는 3 * 3 = 9가 될 것이다.

그림 3

• 이러한 과정의 조건은 \((i, j)\) 위치 값이 0이 아닐 때이다 (다른위치는 0이여도 상관이 없다).
  • 그 이유를 위에서 언급했던 첫 번째, 두 번째 그림 예시를 통해 보자.

그림 4

• \((i, j)\) 외에 다른 위치 값이 0이어도, 빨간 테두리로 둘러싸인 값들이 아래 그림과 같이 이후 초록 테두리로 둘러싸인 부분에서 최대 정사각형 변을 구할 때 영향을 미칠 수도 있기 때문이다.
  • 하지만, \((i, j)\) 위치가 0이라면 그 부분은 웅덩이가 있어 길을 건널 수 없는 것과 같으므로 그림 3의 아랫부분과 같이 진행하지 않는다.

그림 5

 

Code

public int solution(int[][] board) {
    int answer = 0, row = board.length, col = board[0].length;
    int[][] map = new int[row + 1][col + 1];
 
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            map[i + 1][j + 1] = board[i][j];
        }
    }
 
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            if (map[i][j] != 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;
}

 

결과

9
4