[Baekjoon(백준)][15686번] 치킨 배달(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "치킨 배달" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 크기가 N×N인 도시에서 집과 치킨집의 위치가 주어질 때, 도시의 치킨 거리를 최소로 하는 M개의 치킨집을 선택하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

15686번: 치킨 배달

문제 개요

"치킨 배달" 문제는 크기가 N×N인 도시에서 집과 치킨집의 위치가 주어질 때, 도시의 치킨 거리를 최소로 하는 M개의 치킨집을 선택하는 문제입니다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합으로 정의됩니다.

해결 전략

이 문제를 해결하기 위한 전략은 두 가지 단계로 나뉩니다.

1. 가능한 모든 치킨집의 조합을 생성합니다.
2. 각 조합에 대해 도시의 치킨 거리를 계산하고, 최솟값을 찾습니다.

코드 구현

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

using namespace std;

int r, c; // 도시의 크기와 최대 치킨집 개수
vector<pair<int, int>> chikens; // 치킨집 위치
vector<pair<int, int>> houses; // 집의 위치
vector<vector<int>> chickenList; // 모든 치킨집 조합

// 가능한 치킨집 조합 생성 함수
void combi(int start, vector<int> v) {
    if (v.size() == c) {
        chickenList.push_back(v);
        return;
    }
    for (int i = start + 1; i < chikens.size(); i++) {
        v.push_back(i);
        combi(i, v);
        v.pop_back();
    }
}

int main() {
    cin >> r >> c;
    for (int y = 0; y < r; y++) {
        for (int x = 0; x < r; x++) {
            int temp;
            cin >> temp;
            if (temp == 2)
                chikens.push_back({ y,x });
            if (temp == 1)
                houses.push_back({ y,x });
        }
    }
    
    // 모든 치킨집 조합 생성
    vector<int> v;
    combi(-1, v);
    
    int result = INT_MAX;
    // 각 치킨집 조합에 대해 도시의 치킨 거리 계산
    for (vector<int> chiList : chickenList) {
        int ret = 0;
        for (int i = 0; i < houses.size(); i++) {
            int m = INT_MAX;
            for (int j = 0; j < chiList.size(); j++) {
                int dist = abs(houses[i].first - chikens[chiList[j]].first) + abs(houses[i].second - chikens[chiList[j]].second);
                m = min(m, dist);
            }
            ret += m;
        }
        result = min(result, ret);
    }
    cout << result << "\n";
    return 0;
}

코드 설명

• 이 코드는 주어진 도시에서 모든 가능한 치킨집 조합을 생성한 후, 각 조합에 대해 도시의 치킨 거리를 계산합니다. 계산된 치킨 거리 중 최솟값을 찾아 출력합니다.
• combi 함수는 재귀적으로 치킨집의 조합을 생성합니다.
• 메인 함수에서는 각 집마다 치킨집 조합을 통해 계산된 치킨 거리를 더해 최종 도시의 치킨 거리를 구하고, 이 중 최소값을 결과로 출력합니다.

결론

"치킨 배달" 문제는 조합과 완전 탐색을 이용해 해결할 수 있으며, 문제의 조건에 맞는 모든 치킨집 조합을 고려하여 최적의 결과를 도출해낼 수 있습니다.