[백준/구현/백트래킹/C++] 15686번 치킨배달 (삼성 SW 역량 테스트 기출)

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

15686번: 치킨 배달

문제 해결 방법

처음에 도시의 정보를 입력받을 때 1일때는 vector h에, 2일때는 vector ch에 좌표를 넣어준다

if(x==1) h.push_back({i,j}); // 집인 경우
else if(x==2) ch.push_back({i,j}); // 치킨집인 경우

그리고 전체 치킨집의 수와 m을 비교하여 조건을 나눠서 구현했다

 

1. 치킨집의 수가 m보다 클때 ( 전체 치킨집에서 m개를 골라야 할때)

백트래킹을 사용해서 폐업하지 않을  m개를 고른다

// 치킨집 m개 고르기
void pick(int index, int k){ // 이전 선택 인덱스, 총 고른 치킨집 수
    if(k==m){ // m개 골랐을 때
        result = min(result, solve());
        return;
    }
    for(int i=index+1; i<ch.size(); i++){
        if(!isused[i]){
            isused[i] = true;
            arr[k] = i;
            pick(i, k+1);
            isused[i] = false;
        }
    }
}

 

m개를 고랐으면 도시의 치킨거리를 구한다

// 치킨거리 구하기
int solve(){
    int ans =0;
    for(int i=0; i<h.size(); i++){
        int tmp =2e9;
        for(int j=0; j<m; j++){
            tmp = min(tmp,abs(h[i].first-ch[arr[j]].first)+abs(h[i].second-ch[arr[j]].second));
        }
        ans += tmp;
    }
    return ans;
}

 

이렇게 치킨집  m개를 골랐을 때 마다 치킨거리를 구해서 최소를  result 에 넣어준다

 

2. 전체 치킨집의 수와 m이 같을 때 (폐업하는 치킨집이 없을 때)

이 때는 m 개를 고를 일이 없기 때문에 치킨거리만 구하는 함수만 돌리면 된다

만들어 놓은 함수에는 m개를 골라 arr[] 에 넣기 때문에 arr[] 만 채워주고 치킨거리를 구하는 함수를 돌린다

for(int i=0; i<m; i++) arr[i] = i;
result = min(result, solve());

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<pair<int, int>> h, ch;
int arr[14];
bool isused[14];
int result = 2e9;
// 치킨거리 구하기
int solve(){
    int ans =0;
    for(int i=0; i<h.size(); i++){
        int tmp =2e9;
        for(int j=0; j<m; j++){
            tmp = min(tmp,abs(h[i].first-ch[arr[j]].first)+abs(h[i].second-ch[arr[j]].second));
        }
        ans += tmp;
    }
    return ans;
}
// 치킨집 m개 고르기
void pick(int index, int k){ // 이전 선택 인덱스, 총 고른 치킨집 수
    if(k==m){ // m개 골랐을 때
        result = min(result, solve());
        return;
    }
    for(int i=index+1; i<ch.size(); i++){
        if(!isused[i]){
            isused[i] = true;
            arr[k] = i;
            pick(i, k+1);
            isused[i] = false;
        }
    }
}

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

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int x;
            cin >> x;
            if(x==1) h.push_back({i,j}); // 집인 경우
            else if(x==2) ch.push_back({i,j}); // 치킨집인 경우
        }
    }

    if(m==ch.size()){ // 폐업하는 치킨집이 없는 경우
        for(int i=0; i<m; i++) arr[i] = i;
        result = min(result, solve());
    } else {
        pick(-1, 0);
    }

    cout << result;

    return 0;
}