[백준] 치킨배달 15686 (Gold 5) - C++

문제 링크: https://www.acmicpc.net/problem/15686

문제 요약

도시에는 집과 치킨집이 있고, 치킨집 중에서 M개만 남겨야 한다. 각 집에서 가장 가까운 치킨집까지의 거리(치킨 거리)를 구하고, 그 합이 최소가 되도록 M개의 치킨집을 선택하는 문제다. 결국 핵심은 치킨집을 어떻게 고를 것인가이다.

풀이 사고 과정

처음에 든 생각은 단순했다.

• 만약 M이 치킨집 개수와 같다면 그냥 전부 사용하면 된다.
• 그런데 M이 더 작다면, 일부를 골라야 한다.

결국 “치킨집 중에서 M개를 고르는 문제”이고, 이건 조합 문제다.

그래서 백트래킹으로 조합을 만들기로 했다.

치킨집의 위치들을 pair 형태로 저장하고, 그 인덱스를 기준으로 조합을 생성한다. 조합이 하나 완성되면 그 조합을 기준으로 도시 치킨 거리를 계산한다. 모든 조합을 다 돌면서 최솟값을 갱신하면 된다.

 

거리 계산은 BFS 같은 탐색을 할 필요가 없다.

이미 집과 치킨집의 좌표를 알고 있으니 거리 공식 |y1 - y2| + |x1 - x2|만 쓰면 된다. 괜히 주변을 탐색하는 게 더 비효율적이다.

 

치킨집 개수가 최대 13개라는 점도 중요하다. 조합의 최대 경우의 수는 C(13, M)이고, 이 정도면 완전탐색으로 충분히 가능하다고 판단했다. 그래서 복잡한 알고리즘을 고민하지 않고 조합 + 거리 계산으로 밀어붙였다.

전체 코드 흐름

이 코드는 크게 세 단계로 구성된다.

1. 입력 처리

• n, m 입력
• 도시 정보를 한 칸씩 읽는다
  • 집이면 houses 배열에 좌표 저장
  • 치킨집이면 chickens 배열에 좌표 저장

2. 치킨집 조합 생성 (백트래킹)

choosing_chicken(현재 선택 개수 d, 탐색 시작 인덱스 idx)

    만약 d == m 이면
        현재 선택된 치킨집 인덱스 집합으로
        도시 치킨 거리 계산
        최솟값 갱신
        return

    for i = idx부터 마지막 치킨집까지
        i번 치킨집 선택
        choosing_chicken(d+1, i+1)
        선택 취소 (backtracking)

이 구조가 전형적인 조합 생성 방식이다.
i+1로 넘겨주기 때문에 중복 없이 조합이 만들어진다.

3. 도시 치킨 거리 계산

calculate_d(선택된 치킨집 인덱스 집합)

    total_distance = 0

    모든 집에 대해
        min_distance = 매우 큰 값

        선택된 치킨집 각각에 대해
            현재 집과의 거리 계산
            가장 작은 값 갱신

        total_distance += min_distance

    return total_distance

집 하나당 가장 가까운 치킨집을 찾고, 그 거리들을 전부 더하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

void choosing_chicken(int i,int j);
int m;
vector<vector<int>> idx_choices;
vector<pair<int,int>> chickens;
vector<int> visited; //치킨 배열의 인덱스 저장하는 배열
vector<pair<int,int>> houses;

int calculate_d(vector<int> a);

int main(){

    int n;
    cin>>n>>m; //도시 줄과 최대 치킨집 개수

    //만약 m개와 치킨집 개수가 같으면 최단 치킨 거리 합이 정답
    // 만약 m이 더 작다 그러면 골라야 함 -> 고르는 것을 백트래킹으로 효율적으로
    // 하나 하나 더 해보면서 만약 어떤 조건을 넘는다면 그 위치는 폐기 다음 꺼 탐색
    // 치킨 집의 위치들을 pair로 배열에 집어 넣어서 순번을 매김
    // 그걸 조합하는 형식으로 길이를 하나 하나 세보기
    // 생각해보면 길이를 계산하는 것은 단순 덧셈 뺄셈임. 집의 위치를 이미 알고 있으면 매번 주위를 탐색해서 집을 찾는 것보다
    // 미리 기록한 집의 위치 집단 ( 치킨 집 처럼 pair 배열)과 현재 선택한 치킨 집과의 차이 구해서 더 작은 거 계산해두면 됨
    // 치킨집의 개수는 최대 13개니까 아무리 길어도 13번의 계산만 함. 최대 시간 복잡도는 13* (조합 수) 매우 작음 
    
    //정보 입력받기


    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int tmp;
            cin>>tmp;
            if(tmp == 1) houses.push_back({i,j});
            else if(tmp == 2) chickens.push_back({i,j});
        }
    }

    choosing_chicken(0,0);
    int min=INT_MAX;
    for(int i=0;i<idx_choices.size();i++){
        int new_d=calculate_d(idx_choices[i]);
        if(min>new_d){
            min=new_d;
        }
    }

    cout<<min;


    return 0; 
}

void choosing_chicken(int d, int idx){
    // 치킨집의 위치 인덱스들을 저장한 배열 만드는 함수
    if(d==m){
        idx_choices.push_back(visited); //이 길을 골랐을 때 최단거리 push_back
        return;
    }
    for(int i=idx;i<chickens.size();i++) {//chickens 원소 하나 하나
        visited.push_back(i);
        choosing_chicken(d+1,i+1);
        visited.pop_back();
    }
}

int calculate_d(vector<int> idx_chicks){

    int distance=0;

    for(auto[a,b] : houses){
        int real_d=INT_MAX;
        //각 house 별로 가장 가까운 치킨집 거리 계산
        for(int i : idx_chicks){
            auto[y,x]=chickens[i];
            int new_d=abs(y-a)+abs(x-b);
            if(real_d>new_d) real_d=new_d ;
        }
        distance+=real_d;
    }

    return distance;
}

시간복잡도

조합 개수는 C(13, M)이고, 각 조합마다

• 집 개수 H
• 선택된 치킨집 M개

를 비교한다.

따라서 전체 시간복잡도는

O( C(13, M) × H × M )

입력 제한을 보면 충분히 통과 가능한 수준이다.

 

다 풀고 나서 보인 아쉬운 점들

처음에는 “일단 정답부터 만들자”는 생각으로 구현했다. 그런데 다시 보니까 개선할 수 있는 부분이 보였다.

1. 조합을 저장할 필요가 없다

처음 코드는 모든 조합을 벡터에 저장한 뒤, 다시 순회하면서 거리 계산을 했다. 사실 그럴 필요가 없다. 조합이 완성되는 순간 바로 거리 계산을 하고 최솟값을 갱신하면 된다.

흐름이

조합 생성 → 저장 → 다시 순회

가 아니라

조합 생성 → 즉시 계산

으로 바뀌면 더 깔끔해진다. 메모리도 덜 쓰고 구조도 단순해진다.

2. 거리 미리 계산하기

현재는 abs()를 매번 계산한다. 그런데 집 i와 치킨집 j 사이의 거리는 변하지 않는다. 그렇다면 처음에 모든 집-치킨집 사이의 거리를 2차원 배열로 저장해두고, 이후에는 그 값을 가져오기만 하면 된다.

큰 차이는 아닐 수 있지만, 불필요한 연산을 줄이는 방향으로 개선할 수 있다.

3. 가지치기

거리 계산 도중에 누적합이 이미 현재 최솟값을 넘어섰다면 더 계산할 필요가 없다. 그 조합은 더 이상 볼 가치가 없다. 이런 식으로 가지치기를 넣으면 조금 더 백트래킹다운 풀이가 된다.