[Algorithm] 백준 15686번 치킨 배달

백준 15686번 큐빙

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

완전 탐색으로 전부 돌아보면 됩니다.

다른 사람들 코드 보다 깔끔하지도 않고 많이 노력해야겠다.

         

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
#define ll long long
#define MAX_VALUE 1e10
 
struct Pos {
    int x;
    int y;
    Pos() : x(0), y(0) {}
    Pos(int x, int y) : x(x), y(y) {}
};
vector<Pos> chicken;
vector<Pos> house;
vector<Pos> chicken_choice;
vector<bool> chicken_visit;
int N, M;
int chiCnt, houCnt;
ll answer = MAX_VALUE;
void calDistance();
 
void choiceChicken(int pos, int cnt) {
    if (pos == chiCnt || chicken_choice.size() == M) {
        calDistance();
        return;
    }
    for (int i = pos; i < chiCnt; i++) {
        if (!chicken_visit[i] && cnt < M) {
            chicken_visit[i] = true;
            chicken_choice.push_back(chicken[i]);
            choiceChicken(i + 1, cnt + 1);
            chicken_choice.pop_back();
            chicken_visit[i] = false;
        }
        else {
            choiceChicken(i + 1, cnt);
        }
    }
}
 
void calDistance() {
    ll result = 0;
    bool isNotComplete = false;
    for (int i = 0; i < houCnt; i++) {
        ll minVal = MAX_VALUE;
        for (int j = 0; j < chicken_choice.size(); j++) {
            int tempVal = abs(house[i].x - chicken_choice[j].x) + abs(house[i].y - chicken_choice[j].y);
            if (minVal > tempVal) {
                minVal = tempVal;
            }
        }
        result += minVal;
        if (result >= answer) {
            return;
        }
    }
    answer = min(result, answer);
}
int main()
{
    int temp;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> temp;
            if (temp == 1) {
                house.push_back(Pos(i, j));
            }
            else if (temp == 2) {
                chicken.push_back(Pos(i, j));
            }
        }
    }
    chiCnt = chicken.size();
    houCnt = house.size();
    chicken_visit.assign(chiCnt, false);
    choiceChicken(0, 0);
 
    cout << answer;
    system("pause");
    return 0;
}