[백트래킹] 치킨 배달 - 백준 15686번

문제

15686번: 치킨 배달

풀이

💡
1.집과 치킨집을 배열로 빼서 구분하기
- 거리를 구하기 위해서 좌표를 알고 있어야 할 필요가 있음 → 계속 2중 For문을 돌 순 없으니
- 좌표니 pair<int, int> 사용
2.치킨집 들 중 최대 M개만 추출
- N개 중 M개만 추출 ⇒ Combination (조합)
- 최대 M개이기 때문에 1~M개까지 다 구하기 (for문)
- 1개의 조합들, 2개의 조합, M개의 조합 ⇒ vector<vector<pair<int, int> > >
3.모든 조합들 중 도시의 치킨 거리의 최솟값을 계산

백트래킹 코드 중요!

void combination(vector<pair<int, int> >& current, int start, int K) {
    if(current.size() == K) {
        combinations.push_back(current);
        return;
    }

    for(int i=start;i<chicken.size();i++) {
        current.push_back(chicken[i]);
        combination(current, i+1, K);
        current.pop_back();
    }
}

• push → 재귀 → pop
• 사이즈가 차면 끝!

만났던 오류

#include <cmath> // abs
#include <algorithm> // min
#include <climits> // INT_MAX

• include 잘해주기!

코드

https://github.com/KimGyeongLock/CodingTest/blob/main/15686.cpp