치킨배달

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
/*
 *치킨거리 = 집과 가장 가까운 치킨집 사이으이 거리
 *각가의 집은 치킨 거리를 가지고 있음
 *
 *(r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
 *가장 많이 수익을 낼 수 있는 치킨집의 개수는 최대 M개
 *최대 M개를 고르고 나머지 모두 폐업
 *0빈칸, 1집, 2치킨집
 *
 *치킨집중 최대 M개를 고르고 나머지는 모두 폐업, 뭘 골라야 가장 작게될까?
 *
 *[입력]
 * 2<=N <-50(map사이즈) 1M=M<=13 폐업시킬 치킨집 정보
 * 집의 수 <2N, 최소 1개
 * M<= 치킨집 수(남길 치킨집 수) <= 13
 *
 *[풀이]
 *1. N과 M 받기 (맵 사이즈랑 남길 치킨집의 수)
 *2. 치킨집 좌표 선택하기(최대 3개) 범위가 작으니까 백트래킹으로 될듯
 *3. 선택한 치킨집과 가장 가까운 거리를 구하기
 *4. 최소 힙에 넣어서 가장 작은 값 출력하기
 *
 */

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

int N;
int M;
int arr[14];
int isused[14];
priority_queue<int> pq;
int answer = INT_MAX;

void distance(const vector<int> selectedLocation) {
    int sum=0;
    int map[N+1][N+1];
    for(int i=1; i<N+1; i++) {
        for(int k=1; k<N+1; k++) {
            map[i][k] =0;
        }
    }

    for (int i = 0; i < house.size(); i++) {
        int minDistance = INT_MAX;
        for (int k: selectedLocation) {
            int r1 = house[i].first;
            int c1 = house[i].second;
            int r2 = chicken[k].first;
            int c2 = chicken[k].second;

            int distance = abs(r1 - r2) + abs(c1 - c2);
            minDistance = min(minDistance, distance);
        }
        sum += minDistance;
    }
    answer = min(answer, sum);
}

void findChicken(int k, int size) {
    if (k == M) {
        vector<int> selectedLocation;
        for (int i = 0; i < M; i++) {
            //Selected Chicken house
            selectedLocation.push_back(arr[i]);
        }
        //선택한 치킨집과 거리구하는 로직 시작
        distance(selectedLocation);
    }
    int st = 0;
    if (k != 0) st = arr[k - 1] + 1;
    for (int i = st; i < size; i++) {
        if (!isused[i]) {
            arr[k] = i;
            isused[i] = 1;
            findChicken(k + 1, size);
            isused[i] = 0;
        }
    }
}

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

    int n, m;
    cin >> n >> m;
    M = m;
    N = n;

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= n; k++) {
            int x;
            cin >> x;
            if (x == 1) {
                //집인 경우
                house.push_back({i, k});
            } else if (x == 2) {
                //치킨집 경우
                chicken.push_back({i, k});
            }
        }
    }

    //chicken집을 m만큼 선택하는 경우의 수 구하기
    findChicken(0, chicken.size());

    cout << answer;

    return 0;
}

오늘은 구현문제로 유명?한 치킨배달 문제

백트래킹

이 문제는 완전탐색 문제가 섞여있는데 그 이유는 우리가 "어떤 치킨집을 폐업 시킬지 모르기 때문"이다.
우선 가장 적절한 치킨집을 골라야하는데 컴퓨터는 감으로 쏙쏙 골라서 계산할 수 없으니까 다 골라줘야한다는 것이다.
그래서 백트래킹을 통해서 M개의 좌표를 구해준다.
이때 내가 자주 쓰는 조합이 있는데

(자기 자신 제외 -> isused사용)
(이미 선택한거 제외 -> st를 사용해 시작점 조절)
그래서 치킨집을 골라준다.

나머지는 그냥 최소값 구해서 update하는 거라서 생략 ㅎㅎ

REVIEW

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL