[Programmers/C++] [PCCE 기출문제] 10번 / 공원

 

❗ 문제의 입출력 예시에 오류가 있어 문제(그림)에 맞게 입력값을 수정하여 풀이하였습니다. (2024-11-23)

 

 

 

문제

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

문제

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

 

제한 사항

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시 설명

 

❗ 그림을 보면 park의 마지막 요소가 아래와 같이 수정되어야 한다.

    vector<vector<string>> park = {
        {"A", "A", "-1", "B", "B", "B", "B", "-1"},
        {"A", "A", "-1", "B", "B", "B", "B", "-1"},
        {"-1", "-1", "-1", "-1", "-1", "-1", "-1", "-1"},
        {"D", "D", "-1", "-1", "-1", "-1", "E", "-1"}, 
        {"D", "D", "-1", "-1", "-1", "-1", "-1", "F"},
        {"D", "D", "-1", "-1", "-1", "-1", "-1", "F"}	// 📌
    };

 

 

---

 

풀이 

다이나믹 프로그래밍(DP)를 이용해 해결하였다. Maximal Square 문제와 유사하다.

 

🧩 DP 테이블

• `dp[i][j]`에는 해당 좌표 `(i, j)`를 오른쪽 아래 끝으로 하는 정사각형의 최대 변의 길이가 저장된다.
• 주어진 공원 배열(park)과 같은 크기로 생성하며, 0으로 초기화한다.

🧩 점화식

• park[i][j] == "-1" 이라면, (= 빈 자리라면)
  • `dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1`
    • `dp[i-1][j]`: 바로 위쪽 값
    • `dp[i][j-1]`: 바로 왼쪽 값
    • `dp[i-1][j-1]`: 왼쪽 위 대각선 값
    • 이 세 값 중 최소값에 1을 더한 값이 현재 위치 `(i, j)`를 포함하는 정사각형의 최대 변의 길이다.
  • dp의 가장 위쪽 행(`i = 0`)과 왼쪽 열(`j = 0`)은 1로 초기화한다.

dp테이블과 점화식

 

🧩 결과

모든 dp[i][j] 값 중 최댓값(`maxSize`)을 구하고, 입력값`mats`내에서 가장 크면서 `maxSize`를 넘기지 않는 값을 구한다.

 

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int solution(vector<int> mats, vector<vector<string>> park) {
    int answer = -1;
    int maxSize;
    int n = park.size();
    int m = park[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));	// dp 테이블 생성
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (park[i][j] == "-1") {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                }
                else {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                }
                maxSize = max(maxSize, dp[i][j]);	// 최댓값 갱신
            }
        }
    }
    
    sort(mats.rbegin(), mats.rend());
    for (int mat : mats) {
        if (mat <= maxSize) {
            answer = mat;
            break;
        }
    }
    return answer;
}

 

 

 

---