[Algorithm] 삼성전자 코딩테스트 - 치킨 배달(c++)

전체 치킨집을 vector에 넣고 "조합"을 사용하여 m만큼의 치킨집을 선택하여 도시의 치킨거리를 구하는 방식으로 구현했다.

 

자세한 부분은 코드를 보면 알 수 있다.

 

코드 첨부

// 치킨 배달
#include <iostream>
#include <vector>
#include <climits>
 
using namespace std;
 
int n, m;
int city[51][51] = {0, };
vector<pair<int, int>> chicken;
int visited[2500] = {0, };
vector<pair<int, int>> real_chick;
int ans = INT_MAX;
 
void cal()
{
    int total = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(city[i][j]==1){
                int dist = INT_MAX;
                for(int k=0; k<real_chick.size(); k++){
                    int temp = abs(real_chick[k].first-i)+abs(real_chick[k].second-j);
                    dist = min(dist, temp);
                }
                total += dist;
            }
        }
    }
 
    ans = min(ans, total);
}
 
void choose(int idx, int num)
{
    if(num==m){
        real_chick.clear();
        for(int i=0; i<chicken.size(); i++){
            if(visited[i]==true){
                real_chick.push_back(make_pair(chicken[i].first, chicken[i].second));
            }
        }
        cal();
        return;
    }
 
    for(int i=idx; i<chicken.size(); i++){
        if(visited[i]==true) continue;
        visited[i] = true;
        choose(i, num+1);
        visited[i] = false;
    }
}
 
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>city[i][j];
            if(city[i][j]==2){
                chicken.push_back(make_pair(i, j));
            }
        }
    }
 
    choose(0, 0);
 
    cout<<ans<<"\n";
    return 0;
}

 

 

문제 첨부

www.acmicpc.net/problem/15686

15686번: 치킨 배달