프로그래머스 [PCCE 기출문제] 10번 / 공원(C++) -yes6686- 티스토리

프로그래머스 문제 풀이: [PCCE 기출문제] 10번 - 공원

---

문제 설명:

공원 내 특정 구역 정보를 담은 2차원 배열이 주어지고, `-1`은 장애물을 의미합니다. 다양한 크기의 매트를 이용해 장애물에 닿지 않고 배치할 수 있는 가장 큰 매트 크기를 구하는 문제입니다. 주어진 매트 크기 중 가장 큰 매트 크기를 반환합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

// 공원의 각 위치를 나타내는 배열
int arr[51][51];

int solution(vector<int> mats, vector<vector<string>>
    int rows = park.size();        // 공원의 행 수
    int cols = park[0].size();     // 공원의 열 수
    
    // 공원의 각 위치를 -1인지 여부로 초기화
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            arr[i][j] = (park[i][j] == "-1") ? 0 : 1;  // 장애물은 0, 나머지는 1
        }
    }
    
    int maxAns = -1;  // 가장 큰 정사각형 매트의 크기를 저장
    
    // DP를 활용하여 최대 정사각형 크기 계산
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (arr[i][j] == 1) {
                // 현재 위치에서 가능한 최대 정사각형 크기 계산
                arr[i][j] = min({arr[i-1][j], arr[i][j-1], arr[i-1][j-1]}) + 1;
                maxAns = max(maxAns, arr[i][j]);  // 최대 크기 업데이트
            }
        }
    }
    
    // 매트 크기를 내림차순으로 정렬
    sort(mats.rbegin(), mats.rend());
    
    // 주어진 매트 중 최대 크기와 동일하거나 작은 매트 찾기
    for (int mat : mats) {
        if (mat <= maxAns) {
            return mat;
        }
    }
    
    // 적합한 매트가 없는 경우 -1 반환
    return -1;
}

---

코드 설명

• 핵심 알고리즘: 동적 계획법(DP)을 이용하여 최대 정사각형 크기를 계산합니다. 장애물(`-1`)이 포함된 위치는 정사각형에 포함되지 않도록 처리합니다.
• 구현 세부사항:
• `arr[i][j]`는 (i, j)에서 끝나는 가장 큰 정사각형의 한 변의 길이를 저장합니다.
• 3개의 인접 위치(`arr[i-1][j]`, `arr[i][j-1]`, `arr[i-1][j-1]`)의 최소값에 1을 더해 현재 위치의 최대 크기를 계산합니다.
• 매트 크기를 내림차순으로 정렬한 후, 가장 큰 정사각형 크기 이하의 첫 매트를 반환합니다.
• 시간 복잡도 분석:
• DP 배열 계산: O(rows ⋅ cols)
• 매트 정렬: O(n log n), 여기서 n은 매트의 개수
• 최종 탐색: O(n)
• 총 복잡도: O(rows ⋅ cols + n log n)

---

결과

코드는 공원 배열과 매트 리스트가 주어질 때 최대 크기의 매트를 효율적으로 탐색합니다. 효율성을 유지하며 장애물을 고려하는 DP 알고리즘을 적용한 최적의 풀이를 제공합니다.

다른 접근 방식으로, 2차원 segment tree 또는 binary search를 활용하여 정사각형 크기 검사를 더 효율적으로 수행할 수 있는 여지가 있습니다. 이러한 접근법은 특히 공원의 크기가 매우 큰 경우에 유리할 수 있습니다.