광고판 배치와 destroy/repair: 지우고 다시 채우기

문제 구조 요약

광고판 도시 배치는 process(buildings, ads) 안에서 place_ad(adId, buildingId, top, left)를 호출해 광고판을 놓는 문제입니다.

문제 구조는 다음과 같습니다.

항목	내용
건물 수	20개
광고 수	132개
건물 타입	`WAREHOUSE`, `STORE`
점수	`WAREHOUSE`는 `ad.score`, `STORE`는 `ad.score * 2`
금지 조건	건물 밖, 창문 칸, 다른 광고와 겹치기, 같은 광고 재사용
회전	광고는 회전하지 않는다
출력	각 TC의 `SCORE`, 마지막 합산 `SCORE`

이 문제는 단순히 광고를 많이 넣는 문제가 아닙니다. 좋은 광고를 골라야 하고, STORE 보너스를 활용해야 하며, 남은 빈 공간이 나쁘게 쪼개지지 않도록 좌표를 골라야 합니다.

0점에서 first-fit까지

아무것도 하지 않는 process의 점수는 0입니다.

그다음은 가장 단순한 first-fit입니다.

for ad in input_order:
    for building in input_order:
        for top, left in row_major_order:
            if place_ad(ad, building, top, left):
                다음 광고로 넘어간다 // 좌표·건물 반복을 모두 종료

first-fit은 빠르고 구현이 쉽습니다. 하지만 좋은 좌표를 고르지 않습니다. 처음 들어가는 위치에 바로 놓기 때문에 큰 광고가 들어갈 수 있는 공간을 작은 광고가 먼저 잘라 버릴 수 있습니다.

로컬 canPlace를 작성했다면, 같은 위치에 대한 place_ad의 성공·실패 결과와 먼저 대조합니다.

정렬 greedy: 무엇을 먼저 놓을 것인가

first-fit 다음에는 “무엇을 먼저 볼 것인가”를 고칩니다.

이 문제에서는 광고마다 score, h, w가 다르고 STORE는 점수가 2배입니다. 그래서 입력 순서보다 아래 기준이 자연스럽습니다.

광고 순서:
- score가 높은 광고
- score / area가 높은 광고
- 큰 광고를 먼저 넣어야 빈 공간이 덜 망가지는 경우

건물 순서:
- STORE 먼저
- 유효 빈칸이 큰 건물 먼저
- 창문 때문에 모양이 까다로운 건물은 별도 평가

정렬 greedy는 “좋은 물건을 먼저 본다”는 의미입니다. 하지만 이것만으로는 아직 부족합니다. 같은 광고를 같은 건물에 넣더라도 좌표에 따라 이후 공간이 달라지기 때문입니다.

위치 평가식: 어디에 놓을 것인가

이 문제의 분기점은 “놓을 수 있는 첫 위치”와 “나중에도 좋은 위치”를 구분하는 데 있습니다.

건물 폭이 작기 때문에 각 행을 bitmask로 들면 배치 가능 여부를 빠르게 검사할 수 있습니다.

코드 환경: h-contest 설계 조각. 표준 헤더·STL 없이 상태와 탐색 일부를 설명합니다. 문제의 공개 API와 전체 상태 관리에 연결하여 사용합니다.

// 호출 전: 건물 내부 좌표, 1 <= w < 32, x + w <= 32, y + h <= 24 확인
unsigned int occ[20][24];

int canPlaceLocal(int bid, int y, int x, int h, int w) {
    unsigned int mask = ((1u << w) - 1u) << x;

    for (int r = 0; r < h; ++r) {
        if (occ[bid][y + r] & mask) return 0;
    }
    return 1;
}

창문도 처음부터 occ에 넣어 두면, 이후 배치 검사는 “이미 막힌 칸과 겹치는가” 하나로 단순해집니다. 단, 광고를 제거해야 하므로 창문 mask와 광고 mask를 분리해서 복구할 수 있게 해야 합니다.

좌표를 평가할 때는 실제 점수만 보면 부족합니다.

placement value =
    건물 배율을 반영한 실제 점수
  + 벽, 창문, 기존 광고와 붙는 contact 보너스
  - 빈 공간을 얇게 쪼개는 penalty

contact가 높으면 광고가 구석이나 기존 물체에 붙어 빈 공간을 덜 조각내는 경우가 많습니다. 단, contact만 크게 주면 큰 광고가 들어갈 중앙 공간을 잃을 수 있으므로 실제 점수와 같이 봐야 합니다.

탐색 중 제거·복구는 풀이가 가진 로컬 배치에서만 수행합니다. 최종 배치를 고른 뒤 place_ad를 호출합니다. 이미 공개 API로 배치한 광고를 로컬 배열에서 지워도 채점기 상태가 되돌아가지는 않습니다.

작은 local search의 한계

정렬 greedy 이후에는 이미 놓은 광고 하나를 빼고 다른 광고를 넣어 보는 작은 local search를 시도할 수 있습니다.

1. 점수 대비 효율이 낮은 광고 하나를 제거한다.
2. 미배치 광고 중 좋은 후보를 몇 개 넣어 본다.
3. 점수가 오르면 유지하고, 아니면 rollback한다.

광고 하나만 빼서는 빈 공간 구조가 크게 바뀌지 않습니다. 이미 나쁘게 쪼개진 공간은 작은 이동만으로 회복하기 어렵습니다.

2행 4열 보드에서 A와 B가 가운데 두 열을 차지합니다. A만 제거하면 빈 폭이 2라서 폭 3인 C가 B와 겹칩니다. A와 B를 함께 제거하고 C를 넣으면 점수가 6에서 10으로 개선됩니다.

그림 크게 보기

배치 원리만 떼어 낸 작은 예시입니다. 건물 배율은 1로 두고, A·B는 각각 2×1, C는 2×3입니다. A 또는 B만 제거하면 연속 빈 폭은 2라서 C가 들어가지 않습니다. 둘을 함께 제거해야 폭 3을 확보합니다.

큰 destroy/repair

배치 구조를 바꾸려면 한 번에 여러 광고를 지우고 다시 채우는 편이 강합니다.

best = contact-aware greedy 결과

repeat:
    current = best 복사
    광고 여러 개를 제거한다
    제거된 광고와 미배치 광고를 다시 후보로 만든다
    contact-aware greedy로 다시 채운다

    current가 좋아졌으면 best로 채택한다

여기서 중요한 것은 destroy보다 repair입니다. repair가 first-fit이면 큰 destroy를 해도 낮은 품질의 배치로 돌아가기 쉽습니다. 반대로 repair가 위치 평가식을 잘 쓰면, 같은 공간을 더 좋은 모양으로 다시 채울 수 있습니다.

제거 대상을 완전히 무작위로만 고를 필요도 없습니다.

- 최근에 배치한 광고
- 점수 대비 면적 효율이 낮은 광고
- 특정 건물 하나에 놓인 광고 전체
- 창문 주변에서 공간을 많이 막는 광고
- 무작위 제거와 목적 제거를 섞은 후보

remove count는 실험값입니다. 너무 작으면 지역 최적을 벗어나지 못하고, 너무 크면 매번 거의 새로 만드는 것과 비슷해집니다.

예산을 제한한 건물 단위 재탐색

전체 문제를 정확히 푸는 것은 어렵습니다. 하지만 건물 하나만 떼어 내면 후보 수가 줄어듭니다.

for each building:
    현재 building에 놓인 광고를 모두 제거한다
    미배치 광고 중 이 building에 넣어 볼 후보를 고른다
    DFS로 이 building만 다시 채워 본다
    좋아졌으면 채택하고, 아니면 rollback한다

전체는 greedy와 destroy/repair로 넓게 찾고, 작은 부분은 DFS나 DP로 다시 봅니다. 후보를 제한한 부분 문제를 끝까지 풀었다면 그 후보 집합 안에서만 최적성을 말할 수 있습니다. 시간이나 node 방문 수를 소진해 중단했다면 부분 문제의 최적해도 보장하지 않습니다.

DFS의 비용을 줄이는 방법은 보장 범위가 서로 다릅니다.

방법	무엇이 달라지는가
후보·건물·구역 제한	정확히 풀 대상인 부분 문제 자체를 줄임
남은 후보 점수의 안전한 upper bound	best를 넘을 수 없는 가지를 버리며 부분 문제의 최적성은 유지
시간·node 방문 수 제한	아직 가능한 가지를 남기고 중단하므로 최적성 보장이 사라짐

느슨한 upper bound라도 효과가 있습니다. 남은 후보를 모두 넣는다고 가정해도 현재 best를 넘지 못하면 더 내려갈 필요가 없습니다.

Beam Search보다 repair가 먼저일 수 있다

Beam Search는 부분 상태의 평가식이 좋을 때 강합니다. 그런데 이 문제에서는 미완성 배치의 점수를 평가하기 어렵습니다.

초반에 높은 점수 광고를 많이 넣은 후보가 좋아 보여도, 실제로는 큰 광고가 들어갈 공간을 망쳐 최종 점수가 낮을 수 있습니다. 이럴 때는 미완성 후보를 오래 들고 가는 것보다 완성된 답을 많이 만들고 실제 점수로 비교하는 편이 안정적입니다.

완성된 greedy 답 생성
-> destroy/repair로 완성 답끼리 비교
-> 작은 구역 재탐색과 실제 점수 비교

repair가 계속 같은 나쁜 배치를 만들면 반복 횟수나 빔 폭을 늘려도 개선 폭이 작습니다. 제거 개수와 repair 평가식을 따로 바꾸어 비교합니다.

다른 배치 문제

상자 쌓기에서도 작은 이동으로 해소되지 않는 빈 공간이 생깁니다. 일부 배치를 제거한 뒤 다시 채우는 destroy/repair를 비교해 볼 수 있습니다.

성공과 실패를 모두 실행해 보기

제거·재배치·원상복구 실험 · C++17 전체 예제 내려받기

원문의 canPlaceLocal은 전체 제출 코드가 아닌 설계 조각입니다. 새 실행 파일은 위 그림의 2행 4열 보드에서 한 번의 교체 시도만 구현합니다. 건물 배율은 1이고 창문은 없습니다. A와 B는 가운데 두 열을 차지하며 각각 3점입니다. C는 2행 3열입니다. 이 실험의 repair 후보는 C 하나로 제한하며, 제거한 A·B를 다시 넣는 전체 탐색은 수행하지 않습니다.

원래 보드와 점수 6을 보관하고 별도 후보를 복사합니다.
A만 또는 A·B를 함께 제거합니다.
C를 놓을 수 있는 첫 좌표를 찾습니다. 회전은 허용하지 않습니다.
C를 놓았고 점수가 엄격하게 올랐을 때만 채택합니다. 그 외에는 원래 보드 전체를 유지합니다.

입력: removeMask replacementScore 한 줄입니다. removeMask는 A만 제거하는 1 또는 A·B를 제거하는 3, C의 점수는 0부터 1000까지입니다.

입력	시도 결과	최종 점수
`1 10`	B가 가로막아 C를 놓을 수 없음 → 복구	6
`3 10`	C 배치 성공, 6에서 10으로 개선 → 채택	10
`3 4`	C 배치 성공, 점수 하락 → 복구	6

c++ -std=c++17 -O2 destroy-repair.cpp -o repair-demo
echo '3 10' | ./repair-demo

출력 첫 줄은 배치성공여부 채택여부 후보점수 최종점수입니다. 이어서 최종 보드를 두 줄로 출력합니다. 위 입력은 1 1 10 10, CCC., CCC.입니다. 거절된 시도에서는 점수뿐 아니라 보드도 정확히 .AB., .AB.로 돌아옵니다. 공개 place_ad를 호출한 뒤 되돌리는 예제가 아니라, 로컬 후보만 수정하고 마지막에 채택하는 구조입니다.