코드카타 문제
오늘의 코드카타 문제는 과거 백준 문제인 치킨 배달이다.
문제를 요약하자면, N×N 도시에 흩어진 치킨집 중 최대 M개만 남겼을 때, 도시의 치킨 거리가 최소가 되도록 고르는 것이었다.
여기서 한 집의 치킨 거리는 그 집에서 가장 가까운 치킨집까지의 맨해튼 거리고, 도시의 치킨 거리는 모든 집의 치킨 거리를 전부 더한 값이다. 즉, "어떤 치킨집 M개를 남겨야 모든 집이 전체적으로 가장 가까워지는가"를 찾는 문제다.
문제를 보자마자 제약 조건부터 확인했다.
- N은 최대 50, 치킨집은 최대 13개, 집은 최대 2N개.
- 남길 치킨집 M은 1 이상, 치킨집 개수 이하.
여기서 핵심은 치킨집이 아무리 많아야 13개라는 점이었다. 13개 중 M개를 고르는 모든 경우의 수는 최악의 경우에도 C(13, 6) = 1716가지뿐이라, 굳이 효율적인 알고리즘을 짤 필요 없이 모든 조합을 다 만들어보는 완전 탐색으로 충분하다고 판단했다.
그래서 풀이를 두 단계로 나눴다.
- 조합 생성: 전체 치킨집 중 M개를 고르는 모든 경우를 만든다.
- 거리 계산: 고른 M개에 대해 도시의 치킨 거리를 구하고, 매번 최솟값을 갱신한다.
1. 조합 생성
먼저 입력을 받으면서 집의 좌표와 치킨집의 좌표를 각각 따로 모아뒀다. 어차피 거리 계산에 필요한 건 좌표뿐이라, 격자 전체를 들고 다닐 필요 없이 좌표 리스트만 있으면 된다.
조합은 백트래킹으로 만들었다. select(index, depth)에서
index: 다음에 고를 수 있는 치킨집의 시작 인덱스 (이미 고른 것 뒤에서만 고르게 해서 중복·순서 뒤바뀜 방지)depth: 지금까지 고른 치킨집 개수
depth가 M에 도달하면 한 조합이 완성된 것이므로 거리 계산으로 넘어가고, 아직이라면 index부터 끝까지 하나씩 골라(push) → 재귀 → 다시 빼면서(pop) 모든 조합을 훑는다.
위처럼 [0,1,2,...] 중 M개를 고르는 가지치기를 그려보면, 한 번 고른 인덱스 뒤에서만 다음을 고르기 때문에 같은 조합이 두 번 생기지 않는다는 걸 알 수 있다.
2. 거리 계산
조합 하나가 완성될 때마다 calculate_distance()를 호출한다. 여기서는 모든 집을 돌면서, 각 집에서 고른 치킨집들까지의 거리 중 최솟값을 구해 전부 더한다.
거리는 맨해튼 거리 공식으로 바로 구할 수 있다. 임의의 두 칸 사이 거리가 |r1 - r2| + |c1 - c2|로 정의돼 있고, 중간에 벽 같은 장애물이 없기 때문이다.
이렇게 구한 도시의 치킨 거리를 전역 최솟값 city_dist와 비교해 더 작으면 갱신한다. 모든 조합을 다 돌고 나면 city_dist가 정답이 된다.
코드
// Date: 2026-06-17
// BOJ 15686
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m;
vector<vector<int>> v;
vector<pair<int, int>> house; // 집 좌표
vector<pair<int, int>> chicken; // 치킨집 좌표
vector<pair<int, int>> selected_chicken; // 현재 고른 치킨집 조합
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int city_dist = 999999; // 도시의 치킨 거리 최솟값
// 고른 치킨집 조합에 대해 도시의 치킨 거리를 구하고 최솟값 갱신
void calculate_distance()
{
int total = 0;
for (int i = 0; i < house.size(); ++i)
{
int min_dist = 999999;
for (int j = 0; j < selected_chicken.size(); ++j)
{
// 집과 치킨집 사이의 맨해튼 거리
int dist = abs(house[i].first - selected_chicken[j].first)
+ abs(house[i].second - selected_chicken[j].second);
// 그 집에서 가장 가까운 치킨집까지의 거리
min_dist = min(min_dist, dist);
}
total += min_dist; // 모든 집의 치킨 거리 합산
}
city_dist = min(city_dist, total);
}
// 전체 치킨집 중 M개를 고르는 모든 조합을 백트래킹으로 생성
void select(int index, int depth) {
if (depth == m)
{
calculate_distance();
return;
}
for (int i = index; i < chicken.size(); ++i)
{
selected_chicken.push_back(chicken[i]); // 고르고
select(i + 1, depth + 1); // 다음 인덱스부터 재귀
selected_chicken.pop_back(); // 빼면서 백트래킹
}
}
int main() {
cin >> n >> m;
v.resize(n);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
int a;
cin >> a;
v[i].push_back(a);
if (a == 1) house.push_back({ i, j }); // 집
if (a == 2) chicken.push_back({ i, j }); // 치킨집
}
}
select(0, 0);
cout << city_dist;
return 0;
}