[BOJ] C++ 15686: 치킨 배달 - 조합(combination) 계산하여 완전 탐색

15686번: 치킨 배달

예제가 굉장히 많으므로 백준 링크에서 보시길 바랍니다.

---

50 * 50 보드에서 최대 13개의 치킨집 중 M개를 고르고, 치킨 거리의 최솟값을 계산하면 된다. 13개의 치킨집 중 6개의 치킨집만 남겨야 할 때 최대 경우의 수 13C6 = 1716에, 모든 조합에 대해 거리를 계산하는 6 * 100 개만큼의 데이터만 계산하면 되므로 무조건 1초 안에 해결이 가능하다. 이를 근거로 완전 탐색을 구현했다.

 

구현 사항

1. (a, b)의 집과 치킨집 거리 계산
2. 치킨집 m개의 모든 조합 계산 -> next_permutation() 활용, 주의 사항으로 next_permutation은 정렬된 배열에서만 작동한다.

구현 사항 2번에서 조합을 계산하는게 어려울 수 있는데 전에 백트래킹 문제를 풀면서 이미 조합을 구현해 본 적 있어서 쉽게 해결했다. 잘 모르겠으면 아래 문제를 먼저 풀어보자.

[BOJ] C++ 1941: 소문난 칠공주 - BFS와 백트래킹 섞어 쓰기

나는 구현할 때 먼저 이정도 사항만 정리해 두고 일단 구현하면서 필요한 걸 하나씩 추가했다. 예를 들어 이 문제는 치킨집과 집의 위치를 따로 저장해 두면 굉장히 편했는데, 처음부터 그런 느낌이 들긴 했지만 정확히 필요할 때까지 구현하지 않고 필요할 때 구현했다. 조급해하지 말고 천천히 구현하면서 보충해도 늦지 않다.

 

조합을 계산하기 위해 먼저 치킨집을 일차원 배열에 저장해야 한다. 이를 위해서 치킨집의 위치만 저장한 chicken 벡터를 생성했고, 일차원 배열로 치킨집의 index만 저장하여 조합을 계산하기 위한 초기 세팅을 해두었다.

// m개의 치킨집 조합을 구하기 위한 초기 설정
vector<bool> permutation(chicken.size(), true);
fill(permutation.begin(), permutation.begin() + chicken.size() - m, false);
int res = 999999;

 

그리고 m개의 치킨집에 대해 모든 집과의 거리를 계산해주면 되는데, 거리 계산은 사실 굉장히 쉽다. 여기서 모든 집의 위치만 알면 바로 거리를 계산할 수 있으므로 house 벡터로 집의 위치만 저장해 두었다.

do
{
    int res_cur = 0;
    for (auto cur_house : house)
    {
        // cur_house와 permutation 배열의 값이 1인 index의 치킨집간의 거리 중 최소값을 구해보자.
        int min_cur = 999999;
        for (int i = 0; i < permutation.size(); i++)
        {
            if (!permutation[i])
                continue;
            // chicken[i]와 cur_house의 거리 중 최소값을 구하면 된다.
            min_cur = min(min_cur, abs(chicken[i].first - cur_house.first) + abs(chicken[i].second - cur_house.second));
        }
        res_cur += min_cur;
    }
    res = min(res, res_cur);
} while (next_permutation(permutation.begin(), permutation.end()));

 

next_permutation 함수만 알고 있다면 쉽게 해결 가능한 문제였다.

/** 시뮬레이션 15686 치킨 배달 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, m;
int city[55][55];
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            cin >> city[i][j];
            if (city[i][j] == 1)
                house.push_back({i, j});
            if (city[i][j] == 2)
                chicken.push_back({i, j});
        }
    // m개의 치킨집 조합을 구하기 위한 초기 설정
    vector<bool> permutation(chicken.size(), true);
    fill(permutation.begin(), permutation.begin() + chicken.size() - m, false);
    int res = 999999;

    do
    {
        int res_cur = 0;
        for (auto cur_house : house)
        {
            // cur_house와 permutation 배열의 값이 1인 index의 치킨집간의 거리 중 최소값을 구해보자.
            int min_cur = 999999;
            for (int i = 0; i < permutation.size(); i++)
            {
                if (!permutation[i])
                    continue;
                // chicken[i]와 cur_house의 거리 중 최소값을 구하면 된다.
                min_cur = min(min_cur, abs(chicken[i].first - cur_house.first) + abs(chicken[i].second - cur_house.second));
            }
            res_cur += min_cur;
        }
        res = min(res, res_cur);
    } while (next_permutation(permutation.begin(), permutation.end()));
    cout << res << '\n';
}