프로그래머스 161990 - 바탕화면 정리 Lv.1

출처: https://school.programmers.co.kr/learn/courses/30/lessons/161990

// 프로그래머스 161990 - 바탕화면 정리 Lv.1
// https://school.programmers.co.kr/learn/courses/30/lessons/161990

// 문제 설명
// 격자판 바탕화면에서 빈칸은 '.', 파일이 있는 칸은 '#'이다.
// 한 번의 드래그로 모든 파일을 선택하되 드래그 거리 |rdx-lux| + |rdy-luy|를
// 최소화하는 시작점 (lux, luy)와 끝점 (rdx, rdy)를 [lux, luy, rdx, rdy]로 반환한다.
// 시작점은 사각형의 왼쪽 위, 끝점은 오른쪽 아래 격자점이다.

// 제약 조건
// 1 <= wallpaper 길이, 원소 길이 <= 50 (모든 원소 길이 동일)
// 칸은 '#' 또는 '.'만 가지며 파일은 적어도 하나 존재
// lux < rdx, luy < rdy

// 접근 — 모든 '#'을 감싸는 최소 경계 사각형(bounding box)
// 드래그 거리는 |Δ행| + |Δ열|이므로, 사각형을 파일들의
// 최소/최대 행·열에 딱 맞추는 것이 항상 최소다.
// 격자 전체를 한 번 순회하며 '#' 칸의 r1(최소 행)·c1(최소 열)·
// r2(최대 행)·c2(최대 열)를 갱신한다.
// 칸 (i, j)를 포함하려면 끝점 격자점은 그 칸의 오른쪽 아래 (i+1, j+1)이어야
// 하므로 끝점에 +1 보정해 [r1, c1, r2+1, c2+1]을 반환한다.
// 시간 O(N*M), 공간 O(1).

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> wallpaper)
{
    int n = wallpaper.size(), m = wallpaper[0].size();
    int r1 = n, c1 = m;     // 파일이 있는 최소 행·열
    int r2 = -1, c2 = -1;   // 파일이 있는 최대 행·열

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (wallpaper[i][j] == '#')
            {
                if (i < r1) r1 = i;
                if (j < c1) c1 = j;
                if (i > r2) r2 = i;
                if (j > c2) c2 = j;
            }

    // 시작점은 칸의 왼쪽 위 격자점, 끝점은 칸의 오른쪽 아래 격자점이라 +1
    return {r1, c1, r2 + 1, c2 + 1};
}

정리

• 드래그 거리

  Δ행

  +

  Δ열

  을 최소화하는 사각형은 모든 #의 최소 경계 사각형으로 항상 결정된다. 후보를 탐색할 필요 없이 min/max만 추적하면 된다.

• 격자 한 번 순회(O(N·M))로 r1·c1(최소 행·열), r2·c2(최대 행·열)를 갱신한다. 최대 50×50이라 여유.
• 좌표가 칸이 아니라 격자점이라는 게 함정 — 칸 (i, j)를 포함하는 끝점은 (i+1, j+1)이므로 반환 시 r2+1, c2+1로 보정한다. 예제 4(["..","#."] → [1, 0, 2, 1])가 정확히 이 케이스.
• 파일이 최소 하나 보장되므로 초기값(r1=n, c1=m, r2=-1, c2=-1)이 남는 경우는 없다.