백준 15686 : 치킨 배달

문제 링크입니다 https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

1. 도시의 정보 중 빈칸을 제외한 치킨집과 집의 좌표를 vector를 사용해 입력받는다.

   (어차피 이 문제의 경우 거리를 구해야 하는 문제이기 때문에 빈칸의 좌표가 필요 없었습니다!)

 

2. 모든 치킨집 중에서 M개를 고른다.

3. 모든 집들에 대해서 고른 M개의 치킨집과의 거리를 구하고 그 중 최솟값이 그 집의 '치킨 거리'이다.

4. 모든 집들에 대해 3번에서 구한 '치킨 거리들의 합'들 중에서 최솟값이 정답이다.

 

전체 치킨집 중에서 M개를 골랐을 때의 모든 경우 중에서 치킨 거리가 가장 짧아지는 경우에 도시의 치킨 거리의 최솟값을 출력하는 문제였습니다. 이 문제에서는 도시의 정보 전체를 이차원 배열 형태로 입력받을 필요가 없었습니다.

 

 

[소스코드 + 주석]

 

// [백준] 삼성 SW 역량 테스트 기출 문제 : 치킨 배달(15686)
 
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
const int MAX = 13 + 10;    // 1 <= M <= 13
 
// 좌표를 저장하기 위한 구조체
struct p {
    int y, x;
};
vector <p> home;            // 집의 좌표를 입력받을 vector
vector <p> chicken_jib;     // 치킨집의 좌표를 입력받을 vector
 
bool check[MAX];    // 치킨집을 고를 때 이미 고른 치킨집을 또 고르지 않기 위한 check 배열
int n, m, what, ret, result[MAX];
 
// 좌표를 인자로 받아서 p type으로 바꿔주는 함수
p make_p(int y, int x) {
    p temp;
 
    temp.y = y, temp.x = x;
    return temp;
}
 
// 입력을 받는 함수
void input_info(void) {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &what);
            if (what == 2) chicken_jib.push_back(make_p(i, j));
            else if (what == 1) home.push_back(make_p(i, j));
        }
    }
    ret = 987987987;
}
 
// 치킨집 M개를 고른 후 모든 집들에 대해서 M개의 치킨집과의 거리 중 최솟값을 구하고
// 모든 집들의 치킨 거리를 누적하여 더한 값(도시의 치킨거리)을 반환하는 함수
int getDist(void) {
    int min_dist_sum = 0;    // 도시의 치킨 거리를 구하기 위한 변수
    
    for (int i = 0; i < home.size(); i++) {
        
        int min_dist = 987987987;    // 하나의 집에 대한 치킨 거리를 구하기 위한 변수
        
        for (int j = 0; j < m; j++) {
 
            int hy = home[i].y, hx = home[i].x;    // 집의 좌표
 
            int cy = chicken_jib[result[j]].y;     // 치킨집의 좌표
            int cx = chicken_jib[result[j]].x;    
 
            int temp = abs(hy - cy) + abs(hx - cx);
            min_dist = min(min_dist, temp);
        }
        min_dist_sum += min_dist;
    }
    return min_dist_sum;
}
 
// M개의 치킨집을 골라서 도시의 치킨거리를 최솟값으로 update 해주는 함수
void getResult(int count, int start) {
    if (count == m) {
        int temp = getDist();    // M개의 치킨집을 골랐을 때, 도시의 치킨거리를 받아
        ret = min(ret, temp);    // 최종 결과값에는 최솟값을 찾아서 넣는다
    }
    else {
        // M개의 치킨집을 고르는 과정
        for (int i = start; i < chicken_jib.size(); i++) {
            if (!check[i]) {
                check[i] = true;
                result[count] = i;
                getResult(count + 1, i + 1);
                check[i] = false;
            }
        }
    }
}
 
int solve(void) {
    input_info();
    getResult(0, 0);
    return ret;
}
 
int main(void) {
    printf("%d", solve());
    return 0;
}

 

 

[소스코드]

 

#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
const int MAX = 13 + 10;
 
struct p {
    int y, x;
};
vector <p> home;
vector <p> chicken_jib;
 
bool check[MAX];
int n, m, what, ret, result[MAX];
 
p make_p(int y, int x) {
    p temp;
 
    temp.y = y, temp.x = x;
    return temp;
}
 
void input_info(void) {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &what);
            if (what == 2) chicken_jib.push_back(make_p(i, j));
            else if (what == 1) home.push_back(make_p(i, j));
        }
    }
    ret = 987987987;
}
 
int getDist(void) {
    int min_dist_sum = 0;
    for (int i = 0; i < home.size(); i++) {
        int min_dist = 987987987;
        for (int j = 0; j < m; j++) {
            int hy = home[i].y, hx = home[i].x;
            int cy = chicken_jib[result[j]].y;
            int cx = chicken_jib[result[j]].x;
 
            int temp = abs(hy - cy) + abs(hx - cx);
            min_dist = min(min_dist, temp);
        }
        min_dist_sum += min_dist;
    }
    return min_dist_sum;
}
 
void getResult(int count, int start) {
    if (count == m) {
        int temp = getDist();
        ret = min(ret, temp);
    }
    else {
        for (int i = start; i < chicken_jib.size(); i++) {
            if (!check[i]) {
                check[i] = true;
                result[count] = i;
                getResult(count + 1, i + 1);
                check[i] = false;
            }
        }
    }
}
 
int solve(void) {
    input_info();
    getResult(0, 0);
    return ret;
}
 
int main(void) {
    printf("%d", solve());
    return 0;
}