1) 문제 분석
처음에는 M개의 치킨집을 고르는 모든 경우를 구하는 계산이 시간이 많이 걸릴거라고 생각해서 다른 방법을 쓸려고 했는데 다시 생각해보니까
치킨집의 최대 갯수가 13개 밖에 되지 않아서 그렇게 오래 걸리지 않다는 걸 깨달았다. M개의 치킨집만 구하면 나머지 연산은 간단하다. 각 집에서부터 가장 가까운
치킨집까지의 거리의 총합이 도시의 치킨거리가 된다. 이렇게 모든 M개의 치킨집의 경우의 수에 대해 치킨 거리를 구해주고 그 중 최솟값이 답이 된다.
최대 M개의 치킨집이라고 했지만, 어차피 M개 내에서 집마다 최소 치킨 거리를 구하기 때문에 M개보다 더 적은 치킨집을 남겨두는 경우에 대해 중복해서
계산해줄 필요는 없다.
2) 재귀 함수의 시간 복잡도
재귀에 대한 이해가 부족해서 항상 단순히 시간 복잡도가 클거야라고 착각해서 다시 짚고 넘어가려고 한다
n개의 원소들의 모든 순열을 구하고자 한다. 이 때의 시간 복잡도를 T(n)이라고 하자.
그러면 T(n) = T(n-1)+T(n-1) = 2T(n-1)이 된다. 결국 T(n) = 2^nT(1) = O(2^n)이 된다.
특히 이 코드에서는 모든 순열을 구하지는 않고, M개의 치킨집이 선택되면 더 이상의 재귀함수 수행을 멈추기 때문에 실제로는 재귀함수 실행 횟수가 이보다는
적을 것이라 생각된다. 재귀함수의 시간복잡도는 이처럼 지수적으로 증가하기 때문에 n의 값이 조금만 커도 수행 속도가 매우 커지게 된다. 하지만 n이 30보다 작으면
1초 안팎으로 실행시간이 그렇게 크지는 않은 것 같다(p44, “Fundamentals of Data Structures in C” 2판 참조).
물론 피보나치에서처럼 메모이제이션을 활용하면 수행속도가 훨씬 개선된다고 한다.
3) 코드
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
int N, M; //N: 도시의 크기 M: 남길 수 있는 최대 치킨집 수
int num_h, num_c; //num_h: 집 수 num_c: 치킨집 수
pair<int,int> houses[100]; //집 위치 배열
pair<int,int> chicken[13]; //치킨집 위치 배열
vector<int> selected; //폐업 안 되는 치킨집 인덱스
int min_dis=INT_MAX; //도시의 최소 치킨 거리
/**
* h와 c 사이의 거리를 구해준다 (|x좌표차|+|y좌표차|)
* @param h :집이 위치한 좌표
* @param c :치킨집이 위치한 좌표
* @return 집과 치킨집 사이의 거리
*/
int distance(pair<int,int> h, pair<int,int> c){
return abs(h.first-c.first)+abs(h.second-c.second);
}
/**
* num_c개의 치킨집 중에서 남길 M개의 치킨집의 조합을 재귀함수를 이용하여 구함
* =>부분집합을 구하는 경우
* @param n :n+1번째 치킨집을 폐업시킬지 남길지 선택함
*/
void solve(int n){
//M개의 치킨집을 다 선택했을 때
if(selected.size()==M){
int total = 0; //치킨 거리 총합
//각 집에 대해서 가장 가까운 치킨 거리를 구한다
for(int i=0; i<num_h; i++){
int closest = distance(houses[i],chicken[selected[0]]);
for(auto it=selected.begin()+1; it!=selected.end(); ++it){
int cost = distance(houses[i], chicken[(*it)]);
//현재 집에서의 가장 작은 치킨 거리 구함
if(cost<closest) closest = cost;
}
//총합에 현재 집에서의 최소 치킨 거리 더함
total += closest;
}
//최솟값 갱신
if(total<min_dis) min_dis = total;
}
//M개 보다 적은 치킨집이 선택되었을 때
else if(n==num_c){
return;
}
//남길 치킨집을 선택한다
else{
//n+1번째 치킨집이 선택됨
selected.push_back(n);
solve(n+1);
//n+1번째 치킨집이 폐업됨
selected.pop_back();
solve(n+1);
}
}
/**
* main 함수
*/
int main(){
int place;
//입력을 받는다
cin >> N; cin >> M;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin >> place;
//집
if(place==1){
//집의 좌표를 저장
houses[num_h].first = i; houses[num_h].second = j;
num_h++; //집 개수 증가
}
//치킨집
else if(place==2){
//치킨집의 좌표를 저장
chicken[num_c].first = i; chicken[num_c].second = j;
num_c++; //치킨집 개수 증가
}
}
}
//M개의 치킨집을 남겼을 때의 치킨 거리 최솟값을 구함
solve(0);
//최소 치킨거리 값 출력
cout<<min_dis;
}