치킨배달_15686

문제 출처 : 치킨배달_15686

파라미터 정리

NxN 맵 크기 (2~50)
1칸은 1x1 크기, 빈 칸(0), 치킨집(2), 집(1) 中 1
(r,c) r : row, c : col 각 값은 1부터 시작함
치킨 거리 = |r1-r2| + |c1-c2| (집과 가장 가까운 치킨집 사이 거리)
M 최대 활성 가능한 치킨 집 수 (1~13)
원하는 것 : 여러 치킨집 중 M개의 치킨집을 선택했을 때 도시의 치킨 거리가 가장 작아질 것

간략한 과정

input_1 N,M 입력받기
input_2 Map[50][50] 초기 맵 정보 입력받기
M개의 치킨집을 선택하는 모든 상황 만들기{
치킨집 활성/비활성을 1 또는 0 비트로 표현하기
for(int i = 0; i < 1<< cnt; i++)로 표현해서 치킨집이 cnt개 있을 때 발생하는 모든 경우의 수 표현
이때 1로 활성화는 치킨집의 수가 M인지 구하는 함수 호출(처음부터 끝까지 1갯수 세서 반환)
호출 결과가 M가 일치할 때 집과 가까운 치킨집 사이의 거리(temp) 구하기
그중 최솟값을 res와 비교하기
}
모든 경우의 수에 대해 res의 값을 비교하고 최솟값을 구하기
output 최솟값(res)를 출력하기

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define INF 9845651

struct loc{
    int r,c;  
};
int N,M;
int Map[50][50];
vector<loc> chicken;
vector<loc> house;

int checkbit(int input){
    int res = 0;
    
    do{
        if(input & 1)  res++;
        input = input >> 1;
        
    }while(input>0);
    
    return res;
}

int solve(){
    int res = INF;
    
    int c_size = chicken.size();
    int h_size = house.size();
    for(int i = 1; i < (1<<c_size); i++){
        int open_num = checkbit(i);
        
        if(open_num == M){
            int total_dis = 0;
            for(int k = 0; k < h_size; k++){
                int temp = INF;
                for(int j = 0; j < c_size; j++){
                    if((i >> j) & 1){
                        int r_dis = abs(house[k].r-chicken[j].r);
                        int c_dis = abs(house[k].c-chicken[j].c);
                        temp = min(temp, r_dis+c_dis);
                    }
                }
                total_dis += temp;
            }
            res = min(res,total_dis);
        }
    }
    return res;
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++){
            cin >> Map[i][j];
            if(Map[i][j] == 2)
                chicken.push_back({i,j});
            else if(Map[i][j] == 1)
                house.push_back({i,j});
        }

    cout << solve() <<endl;

    return 0;
}

시행착오

v_0602_pm10:51/테스트 통과

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define INF 98456515

struct loc{
  int r, c;  
};
int N,M;
int Map[50][50];
vector<loc> home;
vector<loc> chicken;

int calcul(loc dst, loc src){
    int sum = abs(dst.r - src.r);
    sum += abs(dst.c - src.c);
    return sum;
}

int checkBit(int n){
    int res = 0;
    do{
        if(n&1) res++;
        n = n >> 1;
    }while(n>0);
    return res;
}

int solve(){
    int res = INF;
    
    int c_size = chicken.size();
    for(int i = 0; i < (1 << c_size); i++){
        if(checkBit(i) == M){
            int sum = 0;
            for(int k = 0; k < home.size(); k++){
                int sub = INF;
                for(int j = 0; j < c_size; j++){
                    if(i & (1<<j)){
                        sub = min(sub, calcul(home[k],chicken[j]));
                    }
                }
                sum += sub;
            }
            res = min(res,sum);
        }
    }
    
    return res;
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Map[i][j];
            if(Map[i][j] == 1)  home.push_back({i,j});
            else if(Map[i][j] == 2) chicken.push_back({i,j});
        }
    }
    cout << solve() << endl;

    return 0;
}