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

문제 링크

15686번: 치킨 배달

 

풀이

조합으로 푼 문제

1. 먼저 값을 입력 받으며 치킨집의 좌표와 집의 좌표를 각각 chicken과 house 벡터에 넣는다.
2. func 함수를 통해 치킨집의 조합을 찾아 최소가 되는 도시의 치킨 거리를 찾는다.
   1. 현재 인덱스인 curIdx부터 chicken.size()-1까지 반복문을 돌며 조합을 만든다. chickenList에는 현재 조합에 들어있는 치킨집의 좌표들이 들어있다.
   2. 왜 반복문이 curIdx부터 실행하냐면, 이전 인덱스 것들은 이전 func함수에서 실행했을 것이므로! 순열이 아닌 조합이기 때문에 (1,2)든, (2,1)이든 같다.
   3. i 인덱스의 치킨집을 조합에 넣었다면, 그 다음 인덱스들을 체크해서 넣어줘야 한다.
   4. 그렇게 만든 치킨집의 조합 사이즈가 m이 됐다면, 조합이 완성됐다는 의미이므로 도시의 치킨 거리를 구해준다.
   5. 각 집에서 조합의 치킨집들까지 거리를 구해서 최소 거리를 dist에 넣어준다. 구한 dist는 최소 갱신 되면 answer에 넣어준다.
3. answer를 출력하면 끝

 

코드

#include <iostream>
#include <vector>
#define INF 101
using namespace std;

vector<pair<int, int>> chicken;
vector<pair<int, int>> house;

int answer = 1301;

void func(int curIdx, vector<pair<int,int>> chickenList, int m) // m개 뽑기
{
    if (chickenList.size() == m)
    {
        int dist = 0; // 해당 조합에 대한 도시의 치킨 거리
        for (int i = 0; i < house.size(); i++)
        {
            int tmp = INF; // 해당 집과 가장 가까운 치킨집 거리
            int hy = house[i].first;
            int hx = house[i].second;
            for (int j = 0; j < chickenList.size(); j++)
            {
                int cy = chickenList[j].first;
                int cx = chickenList[j].second;
                tmp = min(tmp, abs(hy - cy) + abs(hx - cx));
            }
            dist += tmp;
        }
        answer = min(answer, dist);
    }
    for (int i = curIdx; i < chicken.size(); i++)
    {
        chickenList.push_back(chicken[i]);
        func(i + 1, chickenList, m);
        chickenList.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> arr(n, vector<int>(n));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 2)
            {
                chicken.push_back({ i,j });
            }
            else if(arr[i][j] == 1)
            {
                house.push_back({ i,j });
            }
        }

    }

    func(0, {}, m);
    cout << answer;
}