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

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

15686번: 치킨 배달

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<pii> house; //집
vector<pii> chicken; //전체 치킨 집
vector<pii> choice; //선택한 치킨 집 
int arr[51][51];
bool visited[14];
int N, M;
int result = MAX;

void func(int idx, int cnt)
{
    if(cnt == M)
    {
        int sum = 0;
        for(int i=0; i<house.size(); i++)
        {
            auto[y, x] = house[i]; //도시 좌표
            int dist = MAX;
            for(int j=0; j<M; j++)
            {
                auto[yy, xx] = choice[j]; //선택한 치킨 집 좌표
                dist = min(dist, abs(yy-y)+abs(xx-x)); //가장 짧은 거리 저장
            }
            sum += dist;
        }
        result = min(result, sum);
        return;
    }

    for(int i=idx; i<chicken.size(); i++)
    {
        if(visited[i]) continue;
        visited[i] = 1;
        choice.push_back(chicken[i]); //치킨집 선택
        func(i + 1, cnt + 1);
        visited[i] = 0; //백트래킹
        choice.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> arr[i][j];
            if(arr[i][j] == 1) house.push_back({i, j}); //집 위치 저장
            if(arr[i][j] == 2) chicken.push_back({i, j}); //치킨집 위치 저장
        }
    }

    func(0, 0);
    cout << result;

    return 0;
}

집의 위치와 치킨집의 위치를 따로 저장하고 시작한다.

치킨집을 M개를 골라야하는데, M개를 고르는 경우는 여러가지가 존재하므로 이에대해 백트래킹을 해주면서 M개를 골라준다.

 

이렇게 고른 M개의 치킨집이랑 도시의 위치를 계산하여 가장 짧은 거리를 저장해 나가며 이 중에서 가장 짧은 값을 출력한다.

 

난이도 기여 칸의 다른 사람들 의견을 살펴보니 해당 문제는 조합으로도 풀 수 있다는 것을 알았다.

다음에 한번 조합으로 풀어보는 것도 나쁘지 않을 것 같다.