[백준] 15686 치킨배달, 완전탐색

YUN·2026년 3월 20일

C++

목록 보기

79/85

완전탐색으로(프루닝 없이도 시간 통과 가능) 최소 치킨 거리를 찾는 문제이다.

도시에 있는 치킨집 중에서 최대 M개 고르라는데, 당연히 M-1개보다는 M개를 골랐을때 치킨 거리가 더 적은 경우의수가 존재한다. 따라서 치킨집은 M개를 골라야한다.

모든 문제는 처음에 완탐으로 접근하는게 정석이다.

완탐을 하는 경우 연산량은 어떻게될까?

치킨집 M개 뽑는 조합에 대해 전부 확인해줘야하고(13 C m), 각 조합에대해 집 갯수 만큼 확인해줘야하고(2n), 각 집에 대해 치킨집 갯수만큼(m) 조사해줘야한다.

13 C M 2N M 이고, 이는 최대 13C6 x 100 x 13 = 2,230,800

으로 매우 널널하다. (조합은 nCr에서 r이 중간값에 가까워질수록 커진다)

(일일이 계산 전부 안해봐서 m의 값에따라 저게 최댓값이 아닐수도 있긴한데 그래봐야 저 정도 숫자 언저리여서 신경안써도됨)

따라서 완탐으로 풀이가 가능하다.

집과 치킨집은 입력받을때 벡터에 따로 저장해둔다.
(이렇게 안하면 이차원 배열에 전부 저장해두고 순회하면서 일일이 다 찾아야하는데 그러면 시간 복잡도 측면에서 코스트가 매우 커진다)

이후 combi() 돌려서 m개뽑는 조합 완성되면 그때그때 치킨거리의 최소 합 구하는 함수 돌려서 ret을 업데이트한다.

combi()다 돌리고 마지막에 ret() 출력해준다.

1. 풀이

 
     
#include <bits/stdc++.h>
     
using namespace std;

vector<pair<int,int>> c_list;
vector<pair<int,int>> h_list;
int a[54][54];
int n,m;
int ret = 10000

int get_chicken_dist(vector<int> v) {
     int sum = 0;
     for(pair<int,int> p : h_list) {
         int cnt = 200;
         for(int idx : v) {
             cnt = min(cnt, abs(p.first-c_list[idx].first)+abs(p.second-c_list[idx].second));
         }
         sum+=cnt;
     }
     return sum;
 }     
     
void combi(int start, vector<int>& v) {
     if(v.size()==m) {
         ret = min(ret, get_chicken_dist(v));
         return;
     }
     
     for(int i = start+1; i<c_list.size() ; i++ ) {
         v.push_back(i);
         combi(i,v);
         v.pop_back();
     }
 }     
      
int main() {
    int tmp;
    vector<int> v1={};
    cin >> n >> m;
    for (int i=0;i<n;i++) {
       for (int j=0;j<n;j++) {
           cin >> tmp;
           if(tmp == 1) h_list.push_back({i,j});
           else if(tmp == 2) c_list.push_back({i,j});
       }
    }
    combi(-1,v1);
    cout << ret;
    return 0;
}

최소값 잡는게 살짝 애매해서 그냥 안전하게 잡았다.

맵의 최대 크기가 50*50 이고, 따라서 집과 치킨집 사이의 최대 거리는 100 이다.
집은 최대 100개이므로 최솟값의 초기값을 10000 보다 크게 설정하면된다.

2. 오답노트

1. 조합 재귀 구현 코드 외우기

void combi(int start, vector<int>& v) {
     if(v.size()==m) {
         ret = min(ret, get_chicken_dist(v));
         return;
     }
     
     for(int i = start+1; i<c_list.size() ; i++ ) {
         v.push_back(i);
         combi(i,v);
         v.pop_back();
     }
 }

이상하게 조합의 재귀 구현 코드는 항상 까먹는다. 잘 외워두자