[boj] 백준 15686 치킨배달 - DFS, 조합

[문제]

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

15686번: 치킨 배달

 

[풀이]

치킨거리의 합을 가장 작게 만드는 m개의 치킨집을 선택해야 한다. 이는 곧 (1,2,3)을 선택하나 (2,1,3)을 선택하나 똑같기때문에 조합을 만든 후 비교해야 한다. 조합에 대해서는 dfs를 이용해 구현 가능하다. i 번째 치킨집이 조합에 포함되면 check[i]를 true로 바꿔주고 m개의 치킨집에 대한 조합이 완성될 때까지 반복한다. m개의 치킨집에 대한 조합이 완성되면 각 집에 대한 최소의 치킨거리를 구한 후 그 합 역시 최소가 되도록 갱신해준다. 이후 check[i] 을 다시 false로 바꿔주고 selected(선택된 치킨집 조합 벡터)를 pop_back()해주는 것을 잊지 말 것!! 그리고 앞서 얘기했듯 조합에서는 (1, 3)과 (3, 1)이 똑같기 때문에 두 번 체크할 필요가 없다. 따라서 idx를 dfs에 파라미터로 전달해줌으로써 이후의 값만 고려하도록 해야 시간초과가 뜨지 않는다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace::std;
#define MAX 51

int n, m, answer=987654321;
int city[MAX][MAX];
vector<pair<int, int>> res, house, selected;
bool check[13];

int calculate_distance(){
    //selected와 house 간에 치킨 거리의 합
    int sum = 0;
    for(int i=0; i<house.size(); i++){
        int x1 = house[i].first;
        int y1 = house[i].second;
        int m = 987654321;
        for(int j=0; j<selected.size(); j++){
            int x2 = selected[j].first;
            int y2 = selected[j].second;
            int diff = abs(x1-x2) + abs(y1-y2);
            m = min(m, diff);
        }
        sum += m;
    }

    return sum;
}

void dfs(int idx, int depth){
    if(depth==m){
        //거리 비교해서 최솟값이면 answer
        answer = min(answer, calculate_distance());
        return;
    }
    for(int i=idx; i<res.size(); i++){
        if (check[i]) continue;
        check[i] = true;
        selected.push_back(res[i]);
        dfs(i, depth+1);
        check[i] = false;
        selected.pop_back();
    }

}

int main() {
    // 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> city[i][j];
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(city[i][j]==2)
                res.push_back({i, j}); //치킨 집 위치
            else if(city[i][j]==1)
                house.push_back({i, j}); //집 위치
        }
    }

    dfs(0, 0);

    cout << answer;

}