[백준] 15686번 치킨 배달 C++

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

C++

#include<iostream>
#include<algorithm>
using namespace std;

int n,m,final = 1000000000;
int city[51][51];
vector<pair<int,int>> chi;
vector<pair<int,int>> home;
vector<pair<int,int>> finalChi;

// 일단 치킨집, 일반 가정집을 구분해서 저장해야한다.
// 그리고 치킨집 M개 선택하는거니까 조합일거고
// 그 치킨집들에 대한 거리 최솟값을 더함 그게 치킨 거리리니까
// 그럼 치킨집 선택하는 조합 함수, 그 치킨집 거리 최솟값 더하는거

int distance() {
    int sum = 0;
    for(int i = 0; i < home.size(); i++) { // 치킨집 거리
        int dis = 1000000000;
        for(int j = 0; j < m; j++) {
            int x = abs(finalChi[j].first - home[i].first);
            int y = abs(finalChi[j].second - home[i].second);
            dis = min(dis, x+y);
        }
        sum += dis;
    }
    return sum;
}

void search(int c) {
    if(finalChi.size()==m) {
        final = min(final, distance());
    }
    for(int i = c; i < chi.size(); i++) {
        finalChi.push_back(chi[i]);
        search(i+1);
        finalChi.pop_back();
    }
}

int main() {
    // 크기 nxn 도시, 도시의 칸은 (r,c)
    // 치킨거리는 집과 가장 가까운 치킨집 사이의 거리
    // 도시의 치킨 거리는 모든 집의 치킨 거리
    // 0은 빈칸, 1은 집, 2는 치킨 집

    // 도시 치킨집 중에서 최대 m개를 고르고, 나머지 치킨집 모두 폐업
    // 도시의 치킨 거리가 가장 작게 될지

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> city[i][j];
            if(city[i][j] == 1) {
                home.push_back({i,j});
            }
            if(city[i][j] == 2) {
                chi.push_back({i,j});
            }
        }
    }
    search(0);
    cout << final << "\n";
}

문제풀이

• 도시의 치킨 거리의 최솟값과 치킨집을 최대 M개 고른다. 이 두 개의 키워드를 중심으로 문제를 풀었다. 먼저 치킨 거리의 최솟값을 구하기 위해서는 배열로 입력받는 값 중에서 집과 치킨집을 구분해야한다고 생각했다. 그리고 각 집과 선택한 치킨집 사이의 x,y 거리를 구하고 최솟값을 구한다. 그런 다음 그 합을 return한다. 두번째 최대 M개를 고른다에서는 DFS 방법을 사용해야된다고 판단했다. 그래서 고른 치킨집의 개수가 m개일 때는 치킨 거리의 최솟값을 구했다. 아닌 경우에는 계속해서 다른 치킨집을 선택하면서 모든 경우의 수에 대한 치킨 거리를 구했다. for문에서 i = c를 한 이유는 중복을 제거하기 위해서이다.

Comment

• 항상 DFS를 사용한 함수를 작성하면 문제를 풀 수 있었는데 이 문제는 치킨 거리의 최솟값까지 구해야해서 어떤 식으로 문제를 풀어야할지조차 잘 감이 오지 않았다. 점점 문제가 복잡하고 어려워질수록 키워드 파악을 잘하고 그에 대한 함수를 잘 작성해야될 것 같다.