백준 15686 치킨 배달 C++

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

15686번: 치킨 배달

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ15686.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ15686
//
//  Created by Hwayeon on 2021/08/04.
//

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int N, M;
int map[51][51] = {0,};
vector<pair<int, int>> house;
vector<pair<int, int>> chicken_shop;
vector<pair<int, int>> survive_chicken_shop;

int answer = 20001;

int cal_chicken_distance(){
    int chicken_distance = 0;
    for(int h=0; h<house.size(); h++){
        int hx = house[h].first;
        int hy = house[h].second;
        int min_dis = 100;
        for(int c=0; c<survive_chicken_shop.size(); c++){
            int cx = survive_chicken_shop[c].first;
            int cy = survive_chicken_shop[c].second;
            int n_dis = abs(cx-hx) + abs(cy-hy);
            if(min_dis > n_dis){
                min_dis = n_dis;
            }
        }
        chicken_distance += min_dis;
    }
    return chicken_distance;
}

void choose_chicken_shop(int cnt, int idx){
    //폐업시키지 않을 치킨집을 M개 고른 경우,
    if(cnt == M){
        int chicken_distance = cal_chicken_distance();
        if(answer > chicken_distance) answer = chicken_distance;
        return;
    }
    if(M-cnt > chicken_shop.size()-(idx+1)) return;
    for(int i=idx+1; i<chicken_shop.size(); i++){
        survive_chicken_shop.push_back(chicken_shop[i]);
        choose_chicken_shop(cnt+1, i);
        survive_chicken_shop.pop_back();
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> map[i][j];
            //집인 경우,
            if(map[i][j] == 1){
                house.push_back({j, i});
            }
            //치킨 집인 경우,
            else if(map[i][j] == 2){
                chicken_shop.push_back({j, i});
            }
        }
    }
    choose_chicken_shop(0, -1);
    cout << answer << endl;
    return 0;
}

---

풀이 과정

풀이 시간 35분

//
//  main.cpp
//  BJ15686
//
//  Created by Hwayeon on 2021/08/04.
//

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int N, M;
int map[51][51] = {0,};

//집의 위치를 담는 벡터
vector<pair<int, int>> house;
//치킨집의 위치를 담는 벡터
vector<pair<int, int>> chicken_shop;
//폐업하지 않고 남을 치킨집의 위치를 담는 벡터
vector<pair<int, int>> survive_chicken_shop;

//도시의 치킨거리의 최솟값을 최대의 경우로 초기화
//대략 어림잡아 치킨집이 (50,50)에 위치하고 집이 (1,1)에 100개 있는 경우로 적용
int answer = 10000;

//도시의 치킨 거리를 계산하는 함수
int cal_chicken_distance(){
    int chicken_distance = 0;
    for(int h=0; h<house.size(); h++){
        int hx = house[h].first;
        int hy = house[h].second;
        int min_dis = 100;
        for(int c=0; c<survive_chicken_shop.size(); c++){
            int cx = survive_chicken_shop[c].first;
            int cy = survive_chicken_shop[c].second;
            int n_dis = abs(cx-hx) + abs(cy-hy);
            if(min_dis > n_dis){
                min_dis = n_dis;
            }
        }
        chicken_distance += min_dis;
    }
    return chicken_distance;
}

void choose_chicken_shop(int cnt, int idx){
    //폐업시키지 않을 치킨집을 M개 고른 경우, 도시의 치킨거리를 구한다
    if(cnt == M){
        int chicken_distance = cal_chicken_distance();
        if(answer > chicken_distance) answer = chicken_distance;
        return;
    }
    
    //치킨집을 M개 고를 수 없는 경우, return
    if(M-cnt > chicken_shop.size()-(idx+1)) return;
    
    //M개의 치킨집 조합을 구한다
    for(int i=idx+1; i<chicken_shop.size(); i++){
        survive_chicken_shop.push_back(chicken_shop[i]);
        choose_chicken_shop(cnt+1, i);
        survive_chicken_shop.pop_back();
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> map[i][j];
            //집인 경우, house 벡터에 위치 추가
            if(map[i][j] == 1){
                house.push_back({j, i});
            }
            //치킨 집인 경우, chicken_shop 벡터에 위치 추가
            else if(map[i][j] == 2){
                chicken_shop.push_back({j, i});
            }
        }
    }
    //폐업하지 않고 남을 M개의 치킨집을 결정 -> DFS 활용
    choose_chicken_shop(0, -1);
    cout << answer << endl;
    return 0;
}
//시간복잡도 = O(n^3), 공간복잡도 = O(N^2)

최대 연산 횟수를 구해보면, N이 최대 50, M이 최대 6(M은 최대 13이지만 치킨집의 조합공식에서 가장 큰 연산횟수가 나오기 위해서 6으로 설정한다.), 집의 개수 최대 2N = 100, 치킨집의 개수 X는 최대 13인 경우를 생각해볼 수 있다.

즉, 치킨집의 조합 xCm = 13C6 = 1716, 도시의 치킨 거리 계산 2N*M = 2*50*13 = 1300이 소요된다.

최대 연산 횟수 = xCm * 2N * M = 2230800이므로 1초 내에 문제를 풀 수 있다.

---

이전 풀이

//
//  main.cpp
//  BJ15686
//
//  Created by Hwayeon on 2021/04/14.
//

#include <iostream>
#include <vector>
using namespace std;

int city[50][50] = {0, };
int N, M;
struct location{
    int x;
    int y;
};
location loc;
vector<location> house, chicken;
int min_chicken = 987654321;
bool visit[13] = {false, };

void get_chicken_distance(int index, int cnt){
    if(cnt == M){
        int total_chicken_distance = 0;
        for(int h=0; h<house.size(); h++){
            int min_chicken_distance = 987654321;
            for(int c=0; c<chicken.size(); c++){
                if(visit[c]){
                    int chicken_distance = abs(house[h].x - chicken[c].x) + abs(house[h].y - chicken[c].y);
                    if(chicken_distance < min_chicken_distance) min_chicken_distance = chicken_distance;
                }
            }
            total_chicken_distance +=  min_chicken_distance;

        }
        if(total_chicken_distance < min_chicken) min_chicken = total_chicken_distance;
        return;
    }
    if(index >= chicken.size()) return;
    visit[index] = true;
    get_chicken_distance(index+1, cnt+1);
    visit[index] = false;
    get_chicken_distance(index+1, cnt);
}

int main(int argc, const char * argv[]) {
    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] == 1){
                loc.x = j;
                loc.y = i;
                house.push_back(loc);
            }
            else if(city[i][j] == 2){
                loc.x = j;
                loc.y = i;
                chicken.push_back(loc);
            }
        }
    }
    get_chicken_distance(0, 0);
    cout << min_chicken << endl;
    
    return 0;
}