프로그래머스 [PCCE 기출문제] 10번 / <공원 풀이>

 

문제 이해

지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 5, 3, 2 세 종류이고, 사람들이 다음과 같이 앉아 있다면 지민이가 깔 수 있는 가장 큰 돗자리는 3x3 크기입니다.

→ 문제를 보자마자 2차원 격자 문제라는 점을 알 수 있었다.

 

→ 그림과 같은 경우 공원에는 4 × 4 크기의 정사각형 공간이 존재한다. 따라서 4보다 작거나 같은 돗자리 중 가장 큰 값을 고르면 된다고 생각했다.

 

지민이가 가진 돗자리들의 한 변의 길이들이 담긴 정수 리스트 mats, 현재 공원의 자리 배치도를 의미하는 2차원 문자열 리스트 park가 주어질 때 지민이가 깔 수 있는 가장 큰 돗자리의 한 변 길이를 return 하도록 solution 함수를 완성해 주세요. 아무런 돗자리도 깔 수 없는 경우 -1을 return합니다.

→ 입력값과 출력값의 관계를 먼저 정리했다.

---

 

 

설계

일단 문제를 2가지 부분으로 나누면 

1. park에서 가능한 가장 큰 정사각형 돗자리 길이 구하기

2. 1에서 구한 돗자리 길이와 mats배열의 값을 비교해서 가능한 돗자리 구하기

이렇게 나눌 수 있다.

 

2번은 비교적 단순하다. mats 배열을 정렬한 뒤, 1번에서 구한 값보다 작거나 같은 값 중 가장 큰 값을 선택하면 된다.

 

따라서 이 문제의 핵심은 1번,

즉 공원에서 가능한 최대 정사각형 크기를 효율적으로 구하는 것이었다.

 

 

처음 접근과 고민

처음에는 (i, j) 위치를 정사각형의 오른쪽 아래 꼭짓점으로 두고 [i-1][j], [i][j-1], [i-1][j-1] 값을 비교하면 될 것이라 생각했다.

 

2×2 크기까지는 비교적 쉽게 구할 수 있었지만, 3×3, 4×4처럼 돗자리 크기가 커질수록 문제가 생겼다.

• 어디까지 반복하면서 비교해야 하는지 기준을 잡기 어려웠고
• 모든 칸 × 모든 돗자리 크기를 확인해야 한다는 점에서
• 이 방식은 비효율적이라고 느껴졌다

특히

"언제까지 반복해서 비교해야 하는가?" 라는 질문에 명확한 답을 내리지 못했다.

 

---

 

 

동적 계획법(DP) 접근

문제를 계속 살펴보면서 재귀적으로 반복되는 패턴이 보이기 시작했다.

• 작은 크기의 돗자리가 가능하면
• 주변의 가능한 돗자리 크기를 이용해
• 더 큰 돗자리가 가능한지를 판단할 수 있었다

공원 전체에서 가능한 가장 큰 돗자리 크기를 더 작은 돗자리 크기들의 결과를 이용해 구할 수 있었다.

→ 큰 문제를 작은 문제로 쪼갤 수 있다.
→ 같은 계산이 반복된다.

 

이 두 가지 조건을 만족하기 때문에 이 문제는 동적 계획법(DP)을 이용해 해결할 수 있다고 판단했다.

 

 

DP 정의

따라서 다음과 같이 DP를 정의했다.

dp[i][j] = (i, j)를 오른쪽 아래 꼭짓점으로 하는 만들 수 있는 가장 큰 빈 정사각형 돗자리의 한 변 길이

 

---

 

 

문제 풀이

값 세팅

int answer = -1;
        
int h = park.length;
int w = park[0].length;

int[][] can = new int[h][w];
int[][] dp = new int[h][w];
int maxSquare = 0;

for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
        if (park[i][j].equals("-1")) {
            can[i][j] = 1;
        } else {
            can[i][j] = 0;
        }
    }
}

• h, w는 공원의 세로와 가로 길이를 의미한다.
• can 배열은 공원의 해당 위치가 "-1"로 비어 있으면 1, 아니면 0으로 변환한 배열이다.
• dp 배열은 (i, j)를 오른쪽 아래 꼭짓점으로 하는 최대 정사각형 크기를 저장한다.

 

동적계획법 적용

for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
        if (can[i][j] == 1) {
            if (i ==0 || j ==0) dp[i][j] = 1;
            else {
                dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
            }
            if (dp[i][j] > maxSquare) {
                maxSquare = dp[i][j];
            }
        } else {
            dp[i][j] = 0;
        }
    }
}

• 현재 위치가 비어 있다면 돗자리를 놓을 수 있다.
• 가장자리에 위치한 경우 최대 크기는 1이다.
• 그 외의 경우 [i-1][j], [i][j-1], [i-1][j-1] 중 가장 작은 값에 1을 더한다.
• 세 방향 중 하나라도 작으면 더 큰 정사각형을 만들 수 없기 때문에 최소값 기준으로 크기를 확장한다.
• 매 반복마다 maxSquare를 갱신해 공원 전체에서 가능한 최대 크기를 기록한다.

 

정렬

Arrays.sort(mats);
for (int i= mats.length -1; i>=0; i--) {
    if (maxSquare >= mats[i]) {
        answer = mats[i];
        break;
    }
}

• mats 배열을 오름차순으로 정렬한다.
• 가장 큰 값부터 확인하면서 maxSquare보다 작거나 같은 값이 나오면 해당 값을 정답으로 선택한다.
• 끝까지 없다면 -1을 반환한다.

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        
        int h = park.length;
        int w = park[0].length;
        
        int[][] can = new int[h][w];
        int[][] dp = new int[h][w];
        int maxSquare = 0;
        
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (park[i][j].equals("-1")) {
                    can[i][j] = 1;
                } else {
                    can[i][j] = 0;
                }
            }
        }
        
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (can[i][j] == 1) {
                    if (i ==0 || j ==0) dp[i][j] = 1;
                    else {
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    if (dp[i][j] > maxSquare) {
                        maxSquare = dp[i][j];
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        Arrays.sort(mats);
        for (int i= mats.length -1; i>=0; i--) {
            if (maxSquare >= mats[i]) {
                answer = mats[i];
                break;
            }
        }
        
        
        return answer;
    }
}

 

---

 

 

느낀점

동적 계획법 문제는 아직도 쉽지 않다.

 

하지만 이번 문제를 통해

• 큰 문제를 작은 문제로 쪼갤 수 있는지
• 같은 계산이 반복되는지

이 두 가지를 먼저 떠올리는 것이 중요하다는 점을 다시 한 번 느꼈다.

아직 DP가 익숙하지는 않지만, 문제를 많이 풀다 보면 접근 방식이 점점 자연스러워질 것 같다.
다음 DP 문제는 이번보다 조금 더 수월하게 접근할 수 있을 거 같다.