문제
https://school.programmers.co.kr/learn/courses/30/lessons/12905
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 개요
주어진 2차원 배열 board에서 1과 0으로 이루어진 가장 큰 정사각형의 넓이를 계산하는 문제입니다.
접근 방법
이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 효율적으로 해결할 수 있습니다.
1. DP 배열 초기화:
입력 배열과 같은 크기의 DP 배열을 생성합니다. DP 배열의 각 요소는 해당 위치에서 끝나는 가장 큰 정사각형의 한 변의 길이를 저장합니다.
2. 기본 조건 설정:
배열의 첫 번째 행과 첫 번째 열은 원본 배열의 값과 동일하게 설정합니다. 즉, board[i][j]가 1인 경우 dp[i][j]도 1로 설정합니다. 이는 가장자리에 있는 1은 그 자체로 정사각형의 한 변이 될 수 있기 때문입니다.
3. DP 배열 채우기:
2차원 배열을 순회하면서 각 요소가 1인 경우, 해당 위치에서 가능한 가장 큰 정사각형의 크기를 계산합니다.
이때, 현재 위치의 왼쪽, 위쪽, 대각선 위쪽의 값들을 참조하여, 이들 중 최소값에 1을 더한 값을 현재 DP 배열에 저장합니다. 이는 현재 위치에서 정사각형을 확장할 수 있는지를 판단하는 과정입니다.
4. 최대 정사각형 크기 추적:
DP 배열을 업데이트하면서 가장 큰 정사각형의 한 변의 길이를 추적합니다. 최종적으로 이 최대 길이를 제곱하여 넓이를 계산합니다.
class Solution
{
public int solution(int [][]board)
{
int answer = 0;
int[][] dp = new int[board.length][board[0].length];
for(int i=0; i<dp.length; i++) {
for(int j=0; j<dp[0].length; j++) {
if(board[i][j] == 1) {
if(i==0 || j==0) {
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
answer = Math.max(answer, dp[i][j]);
}
}
}
return answer*answer;
}
}
'문제 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 달리기 경주 - Java (1) | 2024.11.24 |
---|---|
[프로그래머스] 멀쩡한 사각형 - Java (0) | 2024.11.23 |
[프로그래머스] 리코쳇 로봇 - Java (0) | 2024.11.22 |
[프로그래머스] 디펜스 게임 - Java (1) | 2024.11.22 |
[프로그래머스] [PCCE 기출문제] 10번 / 데이터 분석 - Java (0) | 2024.11.22 |