[백준/Baekjoon] 15686 치킨배달C++ :: Back tracking

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

15686번: 치킨 배달

---

1. Logic

- 먼저 시간 복잡도를 계산해봤을때 넉넉잡아 계산해도 50 * 50 * 13 * 13을 해도 42만정도가 나오기 때문에 충분히 돌 수 있다. 그러므로 완전탐색 문제인 것을 알 수 있다. 

 

폐업시키지 않을 치킨집의 최대 갯수를 준다고 했는데 치킨집은 많으면 많을 수록 좋기 때문에 다 골라준다고 생각하면 된다. 여기서 폐업시킨다는 뜻은 고르지 않는다로 생각하고 치킨집에 대해 조합탐색을 하여 골라진 치킨집과 집 사이의 최단거리를 구하면 된다.

 

처음엔 최단거리라고 해서 BFS를 생각했지만 중간에 장애물이나 그런것이 없으므로 단순히 좌표만 받아 저장해서 서로간의 치킨 거리를 구해주면 시간복잡도를 더 줄일 수 있다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int>> home;
vector<pair<int, int>> kfc;
vector<pair<int, int>> pick;
bool choice[13];
int answer = 0x3f3f3f3f;

int n, m;

int calcDist(pair<int, int> p, pair<int, int> h) {
    return abs(p.first - h.first) + abs(p.second - h.second);
}

void solve() {
    int temp = 0;

    for(int i = 0; i < home.size(); i++) {
        int minDist = 0x3f3f3f3f;
        for(int j = 0; j < pick.size(); j++) {
            minDist = min(minDist, calcDist(pick[j], home[i]));
        }
        temp += minDist;
    }
    answer = min(answer, temp);
}

void combination(int k, int cnt) {
    if(cnt == m) {
        solve();
    }

    for(int i = k; i < kfc.size(); i++) {
        if(choice[i]) continue;

        choice[i] = true;
        pick.push_back({kfc[i].first, kfc[i].second});
        combination(i, cnt+1);
        choice[i] = false;
        pick.pop_back();
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            int input;
            cin >> input;
            if(input == 1) home.push_back({i, j});
            else if(input == 2) kfc.push_back({i, j});
        }
    }

    combination(0, 0);

    cout << answer;
}

 

 

---

3. Feedback

처음 봤을때 문제가 이해가 안되서 약 1주일정도 공부하고 다시 보니까 문제가 이해도 쉽고 잘 풀린것 같다. 부대 안인데 KFC먹고싶다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐