[algorithm] 백준 - 치킨배달

이 문제는 삼성 SW 기출 문제이다. brute force로 풀었다.

 

치킨집 중에서 m개를 뽑아서 가정집과 치킨집의 차가 가장 적었을 때 얼마인지 구하는 것이다.

 

우선 가정집벡터와 치킨집벡터로 나누어 지도를 입력받을 때 값을 넣어준다.

 

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

 

최대 m개를 뽑아야하므로 m으로 target을 정해 조합으로 풀었다.

 

최대라고 해서 target에 1부터 m까지 대입시켜 함수를 호출했는데

그러지 않고, m을 target에 대입시켜 풀었을 때도 통과하는 걸 보니

굳이 1부터 m까지 반복문을 돌리지 않아도 되나보다.

 

그리고 뽑힌 치킨집과 가정집 사이의 거리 차의 최솟값을 구하기 위해

가정집을 바깥 포문에 위치하고 치킨집을 안쪽 포문에 위치시켜

가장 차가 적은 값을 구한 뒤, 모든 거리 차를 더한다.

그리고 그 거리차 중 가장 작은 값을 구한다.

 

int houseWeight = 0;
        for(int i = 0; i < houseVector.size(); i++){
            int weight = 101;
            for(int j = 0; j < chickenVector.size(); j++){
                weight = min(weight, abs(houseVector[i].first - chickenVector[j].first) + abs(houseVector[i].second - chickenVector[j].second));
            }
            houseWeight += weight;
        }
        minNum = min(houseWeight, minNum);

 

 

전체 코드는 이러하다.

 

//치킨 배달
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int house[50][50];
int minNum = 987654321;
vector<pair<int,int>> houseVector;
void dfs(int target,int index, vector<pair<int,int>> realVector, vector<pair<int,int>> chickenVector){
    if(index > realVector.size()) return;
    if(target == 0){
        int houseWeight = 0;
        for(int i = 0; i < houseVector.size(); i++){
            int weight = 101;
            for(int j = 0; j < chickenVector.size(); j++){
                weight = min(weight, abs(houseVector[i].first - chickenVector[j].first) + abs(houseVector[i].second - chickenVector[j].second));
            }
            houseWeight += weight;
        }
        minNum = min(houseWeight, minNum);
        return;
    }
        chickenVector.push_back({realVector[index].first,realVector[index].second});
        dfs(target - 1, index + 1, realVector, chickenVector);
        chickenVector.pop_back();
        dfs(target, index + 1, realVector, chickenVector);
}
int main(void){
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> chickenVector;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> house[i][j];
            if(house[i][j] == 2){
                chickenVector.push_back({i,j});
            }
            if(house[i][j] == 1){
                houseVector.push_back({i,j});
            }
        }
    }
    vector<pair<int,int>> cVector;
    dfs(m, 0, chickenVector, cVector);
    cout << minNum;
}