이번에는 백준 15686번 치킨 배달 문제를 풀어보았습니다.
문제를 처음 봤을 때 치킨집의 개수가 최대 13개라는 점이 눈에 들어왔습니다.
13개 정도라면 치킨집을 M개 선택하는 모든 경우를 조합으로 구할 수 있다고 생각했습니다.
그래서 먼저 치킨집 조합을 구한 뒤, 해당 조합에서 집들과의 거리를 계산하는 방식으로 구현해보았습니다.
문제 설명
도시에는 집과 치킨집이 존재합니다.
치킨 거리는 특정 집에서 가장 가까운 치킨집까지의 거리이며, 도시의 치킨 거리는 모든 집의 치킨 거리를 더한 값입니다.
치킨집 중 최대 M개만 남기고 나머지를 폐업시킬 때, 도시의 치킨 거리가 최소가 되는 값을 구하는 문제입니다.
풀이 아이디어
먼저 집의 좌표와 치킨집의 좌표를 각각 저장하였습니다.
이후 조합을 사용하여 전체 치킨집 중 M개를 선택하였습니다.
선택된 치킨집 조합이 완성되면 DFS를 이용하여 각 집과 치킨집 사이의 거리를 계산하였습니다.
visited 배열은 house를 y축, chicken을 x축으로 두어 현재 집과 치킨집의 방문 여부를 관리하도록 사용하였습니다.
모든 집에 대한 거리를 계산한 경우 현재까지 계산한 거리와 최솟값을 비교하여 갱신하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
vector<vector<int>> visited;
int N,M;
int chicken_cnt, house_cnt;
int min_cnt = INT_MAX;
int calculate(int house_idx, int chicken_idx) {
int y = house[house_idx].first - chicken[chicken_idx].first;
int x = house[house_idx].second - chicken[chicken_idx].second;
if (y < 0)
y *= -1;
if (x < 0)
x *= -1;
return y + x;
}
void dfs(int idx, int distance, vector<int> live_chicken) {
if (idx > house_cnt-1) {
min_cnt = min(min_cnt, distance);
return;
}
for (int i=0; i<live_chicken.size(); i++) {
if (visited[idx][live_chicken[i]] == 1) continue;
visited[idx][live_chicken[i]] = 1;
int plus_distance = calculate(idx, live_chicken[i]);
distance += plus_distance;
dfs(idx+1, distance, live_chicken);
distance -= plus_distance;
visited[idx][live_chicken[i]] = 0;
}
}
void combi(int start, vector<int> b, int k){
if(b.size() == k){
dfs(0, 0, b);
return;
}
for (int i=start+1; i<chicken_cnt; i++){
b.push_back(i);
combi(i, b, k);
b.pop_back();
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int temp;
cin >> temp;
if (temp == 1) {
house.push_back(make_pair(i, j));
} else if (temp == 2) {
chicken.push_back(make_pair(i, j));
}
}
}
chicken_cnt = chicken.size();
house_cnt = house.size();
for (int i = 0; i < house_cnt; i++) {
visited.push_back(vector<int>());
for (int j = 0; j < chicken_cnt; j++) {
visited[i].push_back(0);
}
}
vector<int> live_chicken;
combi(-1, live_chicken, M);
cout << min_cnt << endl;
return 0;
}풀이 흐름
- 입력을 받으면서 집의 좌표는 house 벡터에, 치킨집의 좌표는 chicken 벡터에 저장합니다.
- house와 chicken의 개수를 저장한 뒤 visited 배열을 생성합니다.
- combi 함수를 이용하여 전체 치킨집 중 M개를 선택하는 모든 조합을 생성합니다.
- 조합이 완성되면 dfs 함수에 선택된 치킨집 목록을 전달합니다.
- DFS에서는 각 집에 대해 선택된 치킨집들과의 거리를 계산합니다.
- 모든 집에 대한 계산이 끝나면 현재 거리와 min_cnt를 비교하여 최솟값을 갱신합니다.
- 모든 조합 탐색이 끝나면 최종 결과를 출력합니다.
구현 포인트
1. 집과 치킨집 좌표 저장
입력을 받으면서 집과 치킨집의 좌표를 각각 저장하였습니다.
if (temp == 1) {
house.push_back(make_pair(i, j));
} else if (temp == 2) {
chicken.push_back(make_pair(i, j));
}이후 거리 계산은 저장된 좌표를 이용하여 진행하였습니다.
2. 치킨 거리 계산
집과 치킨집 사이의 거리는 맨해튼 거리를 사용하였습니다.
int calculate(int house_idx, int chicken_idx)house와 chicken 벡터에서 좌표를 꺼낸 뒤 y축 차이와 x축 차이의 절댓값을 더하여 거리를 계산하였습니다.
return y + x;3. 조합 생성
치킨집 중 M개를 선택하기 위해 조합을 사용하였습니다.
if(b.size() == k){
dfs(0, 0, b);
return;
}선택된 치킨집 개수가 M개가 되면 DFS를 호출하여 해당 조합의 거리를 계산하였습니다.
4. visited 배열 사용
visited 배열은 house를 y축, chicken을 x축으로 두고 생성하였습니다.
vector<vector<int>> visited;각 집이 특정 치킨집을 방문했는지 여부를 확인하기 위해 사용하였습니다.
5. DFS를 이용한 거리 계산
현재 집과 선택된 치킨집 사이의 거리를 계산한 뒤 누적하였습니다.
int plus_distance = calculate(idx, live_chicken[i]);
distance += plus_distance;모든 집에 대한 계산이 끝나면 현재까지 계산한 거리와 최솟값을 비교하여 갱신하였습니다.
if (idx > house_cnt-1) {
min_cnt = min(min_cnt, distance);
return;
}