[프로그래머스/Day 23] 바탕화면 정리 - AABB

1. 분석

프로그래머스의 '바탕화면 정리' 문제는 2차원 평면에서 모든 점을 포함하는 최소 기능 사각형(Bounding Box)을 구하는 전형적인 문제입니다.

 

수학적으로 AABB (Axis-Aligned Bounding Box)를 구하는 것과 동일합니다.

• 입력: #의 좌표 $(rowIndex, colIndex)$들
• 출력: $[min(rowIndex), min(colIndex), max(rowIndex) + 1, max(colIndex) + 1]$

단순히 루프를 도는 것이 아니라, "어떻게 하면 초기값을 안전하게 설정하고, 비교 연산을 최소화하며, 가독성을 높일 것인가"를 고민했습니다.

---

2. 예측

• 초기값: min 값은 가능한 최대값(50 이상)으로, max 값은 가능한 최소값(0)으로 설정하면 첫 비교 시 무조건 갱신됩니다.
• 메모리 구조: std::string::find와 std::string::rfind를 적절히 섞어 쓰면 내부 루프의 반복 횟수를 획기적으로 줄일 수 있지만 CPU 캐시 히트율을 고려해 순차적 접근을 진행해볼 수 있습니다.

---

3. 구현

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

using namespace std;

vector<int> solution(vector<string> wallpaper) {   
    // 초기값을 제한사항 값인 50보다 큰 51로 설정한다.
    int minRow = 51, minCol = 51;
    int maxRow = 0, maxCol = 0;
    
    int rows = wallpaper.size();
    int cols = wallpaper[0].size();
    
    for (int rowIndex = 0; rowIndex < rows; ++rowIndex)
    {
        for (int colIndex = 0; colIndex < cols; ++colIndex)
        {
            // 파일이 있는 칸(#)을 중심으로 점을 갱신한다.
            if (wallpaper[rowIndex][colIndex] == '#')
            {
                minRow = min(minRow, rowIndex);
                minCol = min(minCol, colIndex);
                maxRow = max(maxRow, rowIndex + 1);
                maxCol = max(maxCol, colIndex + 1);
            }
        }
    }
    
    return { minRow, minCol, maxRow, maxCol };
}

---

4. 결과 및 개선 사항

결과: (1, 0)과 (0, 1)이 입력되어도 minRow는 0, minCol은 0으로 정상 수렴하며, maxRow와 maxCol 역시 각각 2로 확장되어 모든 파일을 포함하는 사각형을 정확히 계산합니다.

 

개선:

• 시간 복잡도: $O(N \times M)$으로 동일하지만, 불필요한 string::find 호출을 줄이고 직접 인덱스에 접근하여 오버헤드를 줄였습니다.
• Unreal Engine 연계: 만약 이 로직이 언리얼 엔진의 UI(UMG)나 미니맵 시스템에서 아이콘들을 감싸는 범위를 계산하는 데 쓰인다면, FIntRect 또는 FBox2D 구조체를 사용하는 것이 더 적절합니다.
• 단점: 현재 방식은 모든 셀을 전수 조사합니다. 만약 바탕화면이 매우 크고 파일이 적다면, #의 위치만 별도로 저장해둔 리스트를 순회하는 것이 훨씬 빠를 수 있습니다. (성능 최적화 시 데이터 밀도에 따른 전략 선택 필요)

---

5. 인사이트

코딩 테스트에서 최소/최대 단어가 나오면 가장 먼저 제한 사항 밖의 값으로 초기화하기