설치 일정과 Beam Search: 남길 후보와 실행할 답

Beam Search는 부분 일정 여러 개를 남기고, 각각을 한 방문씩 늘린 뒤 다시 좋은 후보만 추리는 탐색입니다. 이 사례에서는 다음 주택 후보와 여러 방문으로 이루어진 경로 후보를 서로 다른 기준으로 줄입니다.

그림은 폭 K = 2인 설명용 예시입니다. 숫자는 실제 채점 점수 score가 아니라 후보 유지용 평가값 key이며, 모든 부모에서 나온 다음 상태를 모아 상위 K개를 선택합니다. 두 후보가 같은 부모에서 나와도 됩니다.

문제 계약부터 상태로 옮기기

제출 코드가 받거나 호출하는 인터페이스는 다음과 같습니다.

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

#define MAP_SIZE 100

extern void move(int y, int x);
extern void nextDay(void);

void process(int mapInfo[][MAP_SIZE], int posY, int posX);

항목	계약
지도	100 × 100, 각 칸은 빈 칸 또는 타입 1..6 주택
이동	두 좌표의 맨해튼 거리만큼 시간 사용
설치	타입에 따라 60분부터 210분까지 사용
하루	최대 720분
일정	31일, nextDay()는 최대 30번
날짜 변경	사용 시간만 0으로 만들고 현재 위치는 유지
수익	주택별 기본 수익과 480분 이후 분당 200점 수당
방문 상태	설치한 주택은 사라지지만 전달받은 mapInfo는 바뀌지 않음

마지막 항목 때문에 제출 코드는 실제 설치한 주택을 따로 기록해야 합니다. Beam Search 안에서 가상으로 선택한 주택과 실제로 move를 호출해 설치한 주택도 구분해야 합니다.

struct House {
    int y, x, type;
    int used;  // 이전 날짜까지 실제로 설치했는가?
};

하루 경로의 정확한 깊이 상한

가장 짧은 타입 1 설치도 60분이 걸립니다. 이동 시간이 0이어도 하루 최대 방문 수는 다음과 같습니다.

720 / 60 = 12

따라서 하루 경로는 최대 12칸의 고정 배열로 충분합니다.

const int MAX_PATH = 12;

struct State {
    int pos;
    int minute;
    int score;
    int key;
    int count;
    short path[MAX_PATH];
};

여기서 score와 key는 같은 값이 아닙니다.

• score: 이 가상 경로를 실제 실행했을 때 받는 채점 점수
• key: 아직 완성되지 않은 경로를 탐색 중에 살려 둘지 정하는 값

현재 점수가 조금 낮아도 시간을 적게 쓴 경로는 다음 주택을 하나 더 설치할 수 있습니다. 이런 상태를 score만으로 너무 일찍 버리지 않으려면 별도 key가 필요합니다.

왜 한 단계 탐욕으로 끝내지 않는가

현재 위치에서 가장 효율적인 주택 하나만 반복해서 고르면 가까운 주택은 잘 찾습니다. 하지만 첫 선택이 이후 모든 이동 거리를 바꾸므로, 주택이 밀집한 지역으로 들어가는 경로의 가치를 놓칠 수 있습니다.

당장 좋아 보이는 경로:
현재 -> 가까운 A

첫 이동은 조금 길지만 뒤가 좋은 경로:
현재 -> B1 -> B2 -> B3

B1 하나만 보면 A보다 나빠도, B1, B2, B3가 가까이 모여 있으면 하루 전체 수익은 두 번째 경로가 더 높을 수 있습니다.

그렇다고 모든 경로를 만들 수는 없습니다. 주택이 약 400개라면 첫 두 단계만 보아도 후보 수가 크게 늘어납니다. 따라서 이 풀이에서는 한 경로만 남기는 탐욕과 모든 경로를 보는 완전 탐색 사이의 중간 지점으로 Beam Search를 사용합니다.

첫 번째 가지치기: 다음 주택 8개

각 상태에서 미방문 주택을 전부 검사하되, 실제 다음 상태로 만드는 주택은 평가값 상위 8개뿐입니다.

cost = travel + service[type]
candidateKey = price[type] - candidateRate × cost
candidateRate = 1200

후보 단계의 목적은 최종 경로를 평가하는 것이 아니라, 다음 분기 수를 줄이는 것입니다. candidateRate가 너무 크면 멀고 비싼 주택이 후보 목록에 들어오지도 못합니다. 너무 작으면 이동 시간이 긴 주택이 목록을 차지합니다.

const int BRANCH_COUNT = 8;

void keepCandidate(
    int ids[],
    int keys[],
    int &count,
    int id,
    int key
) {
    if (count == BRANCH_COUNT && key <= keys[count - 1]) return;

    int pos = count < BRANCH_COUNT ? count++ : count - 1;
    while (pos > 0 && keys[pos - 1] < key) {
        ids[pos] = ids[pos - 1];
        keys[pos] = keys[pos - 1];
        --pos;
    }
    ids[pos] = id;
    keys[pos] = key;
}

8개짜리 배열에서는 일반 정렬이나 힙보다 이 삽입 코드가 단순합니다. 배열은 항상 평가값 내림차순이고, 이미 8개가 찼을 때 새 후보가 꼴찌보다 나쁘면 즉시 버립니다.

두 번째 가지치기: 경로 상태 32개

각 빔 상태에서 최대 8개를 확장하면 깊이 하나에서 최대 32 × 8 = 256개의 다음 상태가 생깁니다. 이 중 다음 깊이로 넘길 상위 32개를 고릅니다.

beamKey = actualScore - beamRate × usedMinute
beamRate = 1550

예를 들어 두 상태가 다음과 같다고 하겠습니다.

상태	사용 시간	실제 점수	score - 1550 × minute
A	400분	700,000	80,000
B	500분	800,000	25,000

B의 실제 점수가 더 높지만, A는 100분을 덜 썼습니다. 그 시간에 다른 주택을 붙일 가능성을 남기기 위해 탐색 중에는 A를 더 높게 평가합니다.

const int BEAM_WIDTH = 32;

void keepState(State states[], int &count, const State &next) {
    if (count == BEAM_WIDTH &&
        next.key <= states[count - 1].key) return;

    int pos = count < BEAM_WIDTH ? count++ : count - 1;
    while (pos > 0 && states[pos - 1].key < next.key) {
        states[pos] = states[pos - 1];
        --pos;
    }
    states[pos] = next;
}

첫 번째 가지치기가 한 상태 안의 다음 행동을 줄였다면, 두 번째 가지치기는 서로 다른 경로 전체를 비교합니다. 두 단계의 기준과 폭은 서로 다른 파라미터입니다.

왜 1200과 1550을 따로 쓰는가

후보 평가와 상태 평가에 같은 시간 패널티를 써야 할 이유는 없습니다.

파라미터	역할	이 풀이의 값
candidateRate	다음 행동이 분기 목록에 들어올지 결정	1200
beamRate	확장된 전체 경로가 다음 깊이에 살아남을지 결정	1550

후보 단계는 폭넓게 보고, 상태 단계는 전체 시간 효율을 더 엄격하게 보는 설계입니다. 이를 하나의 식으로 합치면 긴 작업을 너무 일찍 제외하거나, 반대로 시간이 많이 든 경로가 빔을 지나치게 차지할 수 있습니다.

480분 이후에는 실제 점수에 분당 200점이 추가됩니다. 실제 수당을 score에 정확히 넣으면 그 구간의 실질 시간 패널티는 다음처럼 자동으로 낮아집니다.

1550 - 200 = 1350점/분

별도의 “야간 모드” 분기를 만들지 않아도 하루 후반에 남은 시간을 더 적극적으로 쓰게 됩니다.

실제 점수 시뮬레이션

후보를 붙일 때는 채점기와 같은 순서로 시간을 계산합니다.

State next = state;
if (state.minute + travel + service[type] > 720) continue;
int startMinute = state.minute;

next.minute += travel + service[type];
next.score += price[type];

if (next.minute > 480) {
    int bonusStart = startMinute > 480 ? startMinute : 480;
    next.score += (next.minute - bonusStart) * 200;
}

startMinute은 이동을 시작하기 전 시각입니다. 현재 시각이 450분이고 이동과 설치가 100분이면 480분 이후 70분만 수당 대상입니다. 현재 시각이 500분이면 같은 100분 전체가 수당 대상입니다.

한 가상 경로 안의 방문 목록과 실제 설치 완료 목록을 함께 검사해 중복 선택을 막습니다.

생존 기준과 실행 기준을 분리한다

탐색 중 상태를 살리는 기준은 key지만, 하루에 실제로 실행할 경로는 score가 가장 높은 상태입니다.

if (next.score > best.score) {
    best = next;
}

best는 깊이 1부터 깊이 12까지 계속 갱신합니다. 그러면 좋은 경로가 반드시 방문 12개를 채우지 않아도 됩니다. 더 이상 효율적인 주택을 붙일 수 없는 짧은 경로도 최종 답이 될 수 있습니다.

계산량을 단계별로 줄이기

주택 수를 H라고 하면 주택 평가 횟수의 중심은 다음과 같습니다.

31일 × 깊이 12 × 빔 32 × H

H <= 399이므로 약 476만 번입니다. 각 상태에서 실제로 만드는 분기는 최대 8개라 한 깊이의 상태 생성 수는 최대 256개입니다.

파라미터 실험 순서

한 번에 여러 값을 바꾸면 어떤 변경이 효과가 있었는지 알기 어렵습니다. 먼저 기준선을 고정하고 한 축씩 비교합니다.

실험	바꿀 값	기록할 값
0	32 / 8 / 1200 / 1550	TC별 점수, 총점, 실행 시간
1	BEAM_WIDTH 24, 32, 40	경로 다양성의 효과와 시간 증가
2	BRANCH_COUNT 6, 8, 10	후보 누락과 상태 생성 비용
3	candidateRate 주변 값	고가 주택과 가까운 주택의 선택 비율
4	beamRate 주변 값	일일 사용 시간과 실제 점수

총점만 기록하지 말고 TC별 점수도 남겨야 합니다. 평균이 올라도 특정 지도 밀도에서 크게 무너지는 파라미터가 있을 수 있습니다. 날짜별로는 아래 값이 유용합니다.

• 720분 중 실제 사용 시간
• 이동 시간과 설치 시간의 비율
• 주택별 기본 수익과 480분 이후 수당
• 하루 방문 수
• 첫 방문 위치와 마지막 위치

시각화에서는 점수만 보지 말고, 낮은 점수의 날짜가 긴 첫 이동 때문인지, 시간이 남았는데 후보를 못 붙인 것인지, 저효율 타입을 많이 고른 것인지 확인합니다.

전체 규칙과 기준 구현은 에어컨 설치 기사 해설에 있습니다.

작은 하루 일정으로 직접 실행하기

빔 폭과 시간 패널티 실험 · C++17 전체 예제 내려받기

위의 원문 코드는 h-contest 풀이의 설계 조각입니다. 아래 실행 예제는 같은 원리를 분리해 살펴보는 하루짜리 축소 모델입니다. 31일 진행, 타입별 설치 시간, 야간 수당, 공개 API 호출은 포함하지 않습니다. 시작 위치는 (0, 0), 이동은 맨해튼 거리, 실제 점수는 방문한 작업의 보상 합입니다. 종료 위치에서 출발점으로 돌아오지 않습니다.

이 모델은 상태마다 가능한 다음 작업을 모두 확장합니다. 따라서 원문의 ‘상태별 상위 8개’ 가지치기는 생략하고, 모든 부모가 만든 후보를 합쳐 key = score - timePenalty × minute 순으로 빔 폭만큼 남깁니다. 동점이면 실제 점수가 큰 경로, 시간이 짧은 경로, 작업 번호가 사전순으로 작은 경로를 택합니다. 최종 best는 모든 깊이에서 가지치기 전에 생성한 후보의 실제 점수로 갱신합니다.

작업	위치 (x, y)	설치 시간	보상
A (0)	(0, 0)	6	9
B (1)	(1, 0)	2	7
C (2)	(2, 0)	2	7

시간 예산 7, 패널티 0일 때 빔 폭 1은 A를 남기고 점수 9로 끝납니다. 폭 2는 B도 남겨 B→C를 발견합니다. 이동·설치 시간은 1 + 2 + 1 + 2 = 6, 점수는 14입니다. 이 예제에서 폭을 늘리면 개선되지만, 휴리스틱 탐색에서 폭을 늘릴 때마다 항상 점수가 오른다는 일반 보장은 없습니다.

입력: 첫 줄 N budget beamWidth timePenalty, 다음 N줄은 x y service reward입니다. 1 ≤ N ≤ 12, 1 ≤ budget ≤ 1000, 1 ≤ beamWidth ≤ 256, 0 ≤ timePenalty ≤ 100, 0 ≤ x,y ≤ 100, 1 ≤ service ≤ 100, 0 ≤ reward ≤ 1000입니다.

3 7 2 0
0 0 6 9
1 0 2 7
2 0 2 7

c++ -std=c++17 -O2 beam-day.cpp -o beam-demo
./beam-demo < input.txt

출력 첫 줄은 score minute, 다음 줄은 0-based 작업 번호 경로입니다. 이 입력의 결과는 14 6과 1 2입니다. 가능한 작업이 없으면 0 0과 빈 경로가 나옵니다. 패널티를 바꾸면 생존 순서는 달라져도, 표시하는 최종 점수에서 시간 패널티를 빼지는 않습니다.