[백준 15686] 치킨 배달

문제 

https://www.acmicpc.net/problem/15686

풀이

해당 문제는 완전 탐색을 통해 풀었습니다.

문제 해결 방법은 우선 집과 치킨집의 좌표를 vector를 사용하여 받았습니다.
그 뒤에 재귀를 통해 전체 치킨집 중에서 M개를 고르고, 고른 좌표들은 따로 저장을 하였습니다.(거리를 잴때 골라진 치킨집만 계산을 하기 위해!) 

M개가 다 선택되면 한번에 거리를 계산하고 최소 거리를 구합니다.

핵심적인 부분은 47~51 라인입니다.

＃ select 함수에서 인자로 k를 넘긴 이유는 중복 선택을 없애고, 순서가 상관 없기 때문입니다.

예를 들어 치킨집이 5개가 있다고 하고 이중 3개를 골라야된다고 해봅시다.

1,1,1 치킨집은 치킨집이 3개가 아니라 1개이므로 중복을 없애 주었습니다.

따라서 처음에는 1,2,3번 치킨집을 고르고 다음에는 1,2,4번 치킨집을 고를것입니다.

그 다음은 1,2,5번 치킨집이고 이가 끝나면 1,3,2번 치킨집을 고릅니다.

근데 뭔가 찜찜하지 않으세요?

1,3,2번 치킨집은.... 1,2,3번 치킨집과 동일하다는 것입니다.

그렇다면 1,3,2번을 고르는것이 아닌 1,3,4번을 고르는 것이 계산 시간에도 더욱 좋겠죠?

# 50번째 라인에서 pop_back()을 해준 이유는 무엇일까요?

M개가 뽑혀 44번줄에서 계산을 실행하고 이도 끝나면 함수를 종료하게 됩니다.
다음 경우의 수를 계산하기 위해서 마지막 수를 빼고 마지막 수의 다음 수를 넣어주는 것이죠.

즉, [1,2,3]을 뽑았을 경우 다음에는 [1,2,4] 뽑힐 수 있도록 해준 것입니다.

코드

#include <iostream>
#include <vector>
#include <cmath>
 
#define MAX 51
#define INF 987654321
 
using namespace std;
 
vector< pair<int, int> > house;
vector< pair<int, int> > chicken;
vector< pair<int, int> > selectChi;
 
int N, M;
int ans = INF;
 
//뽑힌 치킨집들과 집과의 거리를 계산하고
//최소 거리 구하기
void calcDist(){
    int dist[house.size()];
    for(int i = 0; i < house.size(); i++){
        dist[i] = INF;
    }
    
    for(int i = 0; i < selectChi.size(); i++){
        for(int j = 0; j < house.size(); j++){
            int dis = abs(selectChi[i].first - house[j].first) + abs(selectChi[i].second - house[j].second);
            if(dist[j] > dis){
                dist[j] = dis;
            }
        }
    }
    int dap = 0;
    for(int i = 0; i < house.size(); i++){
        dap += dist[i];
    }
    if(ans > dap)
        ans = dap;
}
//재귀호출을 통해 완전 탐색하기
void select(int cnt, int k){
    //치킨집을 M개 뽑았을 때
    if(cnt == M){
        calcDist();
        return;
    }
    for(int i = k; i < chicken.size(); i++){
        selectChi.push_back(chicken[i]);
        select(cnt+1, i+1);
        selectChi.pop_back();
    }
}
 
int main(){
    cin >> N >> M;
    //집과 치킨집 받기
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            int a;
            cin >> a;
            if(a == 1)
                house.push_back(make_pair(j, i));
            if(a == 2)
                chicken.push_back(make_pair(j, i));
        }
    }
    select(0, 0);
    cout << ans << "\n";
    return 0;
}