[C++][15686] 치킨 배달

[문제]

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

---

[문제 풀이]

처음에는 굉장히 어렵게 접근을 하였었다.

백 트래킹을 활용해서 1의 조합들을 모두 구하고 해당 조합이 나올때마다 BFS를 활용해서 거리를 구해서 모든 거리에서의 최소값을 answer로 제출을 하였다.

하지만, 당연히 백 트래킹 + BFS로 가니 시간은 초과가 날 수밖에 없었다.

코드는 복잡해지는데 시간 복잡도도 올라가니 안 좋은 접근 방식이었다.

 

두번째로 생각을 바꿔보았다.

굳이 BFS를 쓸 필요가 없이 1의 위치를 모두 저장해 둔다면 이중 for문을 활용해서 최솟값을 구할 수가 있을테고 시간 복잡도도 더 간소화 될 것이라고 생각했다.

해당 방식을 이용해서 풀었다

 

* 접근 방식은 좋았으나 마지막에 백 트래킹의 접근 방식에서 시간 초과가 날 법한 실수를 저질렀다. 백 트래킹에 관련해서 조금 더 공부하자.

[코드]

#include<iostream>
#include<vector>
#include <algorithm>
#include<queue>
#define endl "\n"
using namespace std;

int n,m;
int visited[15];
int answer = 100000000;
vector<pair<int, int> > delivery; //2를 넣을 벡터
vector<pair<int, int> > chicken; //1을 넣을 벡터.
vector<pair<int, int> > goobne; // 백트래킹을 통해 조합을 만들 벡터

void back_tracking(int k, int cnt){

    if(cnt == m){
        int min_dist;
        int min_answer = 0; //정답값.

        for(int i = 0;i<delivery.size();i++){ //배달갈 위치들
            min_dist = 100000000;
            for(int j = 0;j<goobne.size();j++){ //현재 있는 굽네 매장 위치들.
                min_dist = min(min_dist,abs(delivery[i].first - goobne[j].first) + abs(delivery[i].second - goobne[j].second));
            }
            min_answer += min_dist;
        }
        answer = min(answer,min_answer);
        return;
    }

    for(int i = k; i<chicken.size();i++){ //치킨집 갯수를 굽네에 조합으로 넣자.
        if(visited[i] == 0){
            visited[i] = 1;
            goobne.push_back(make_pair(chicken[i].first,chicken[i].second)); //굽네 매장을 바꿔주자.
            back_tracking(i, cnt + 1);
            goobne.pop_back();
            visited[i] = 0;
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin>>n>>m;
    int temp;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin >> temp;
            if(temp == 2){
                chicken.push_back(make_pair(i,j)); //2라면 매장에 추가해주자.
            }
            else if(temp == 1){
                delivery.push_back(make_pair(i , j)); 
            }
        }
    }

    back_tracking(0,0);
    cout<<answer<<endl;

    return 0;
}

처참한 흔적들....