[백준/C++] #15686 치킨 배달 (Brute Force)

문제

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

 
 

구상

처음에는 어떤 치킨집을 폐업시켜야 할까? 라는 고민을 통해 아래 처럼 풀이를 구상했었다. 
1. bfs로 각각의 집들에서 가장 가까운 치킨집 방문, 치킨거리 갱신 
2. 가장 방문이 많은 치킨집 순으로 최대 m개를 고르고
3. 나머지 치킨집이랑 가까웠던 집들은 다시 거리 계산해야 한다. 
-> 하지만, 방문이 많은 m개 집 고른다 해도 해당 집들이 최소 도시 치킨 거리를 만든다고 장담할 수 없다. 

수정 후 풀이는 다음과 같았다. Brute force!
1. 치킨집 조합 만들기 -> next_permutation 이용!!
2. 각각의 치킨집에 대해 집들의 거리 구하기
3. 거리를 다 합친 도시 치킨 거리들 중 최소값 구하고 출력

next_permutation

next_permutation은 순열을 만들때 보통 사용하는데, 순열을 구할 배열(컨테이너)의 시작과 끝 iterator를 인자로 받는다. 

if (컨테이너에 다음 순열이 존재한다면(=다음 순열이 존재하다면))
    컨테이너의 원소를 해당 순열 순서로 바꾸고, true 반환
else
     false  반환

 
next_permutation을 사용할 때, 주의점은 다음과 같다. 
1. 오름차순으로 정렬된 값을 가진 컨테이너로만 사용 가능하다. 
2. default로 operator < 를 사용해 순열을 생성한다. -> 오름차순으로 순열 생성
3. 중복이 있는 원소들은 중복을 제외하고 순열을 만든다. 
=> 배열 값들을 1로 놓으면, 조합을 구할 수 있다!! -> 해당 문제에서 활용한 방식이다. 
ex) [0, 0, 1, 1] -> [0, 1, 0, 1] -> [0, 1, 1, 0] -> [1, 0, 0, 1] -> [1, 0, 1, 0] -> [1, 1, 0, 0]

{1, 2, 3, 4} 배열의 조합을 구하고 싶다면, 위 0과 1로 이루어진 배열의 값과 인덱스 값를 통해 조합을 구할 수 있다. 
 
*prev_permutation은 내림차순 정렬된 데이터를 받아서 이전 순열로 바꿔준다. 결국, next_permutation과 정반대 순서의 순열을 내놓는다. 
 

do while

while문의 조건을 보기 전에 한 번은 무조건적으로 실행(do)한 뒤 조건을 충족하는지의 여부를 확인한다.
do실행 후 while 조건을 보고, 충족한다면 do를 실행한다. 실행후 다시 while 조건을 확인한다. 만일, while 조건을 충족시키지 않는다면, while문을 탈출한다. 
 

풀이 + 코드

1. 치킨집 조합 만들기 -> next_permutation 이용!!
2. 각각의 치킨집에 대해 집들의 거리(치킨 거리) 구하기
3. 거리를 다 합친 도시 치킨 거리들 중 최소값 구하고 출력

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
/*
15686 치킨배달
*/

int n, m; // 배열 크기, 치킨집 개수
vector<pair<int, int>> houses, chickens; // 집 위치, 치킨집 위치
vector<vector<int>> map; // 지도

// 거리 구하기
int getDistance(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

// 선택된 치킨집 조합에 대해 모든 집의 최소 치킨 거리를 계산하고 합 반환
int calculateChickenDistance(const vector<pair<int, int>>& selectedChickens) {
    int totalDistance = 0;

    for (const auto& house : houses) { // 특정 집과 
        int minDistance = INT_MAX; // climit 사용
        for (const auto& chicken : selectedChickens) { // 선택된 치킨집들 중 하나와의 
            minDistance = min(minDistance, getDistance(house, chicken)); // 최소 거리 계산
        }
        totalDistance += minDistance; // 최종 거리 계산
    }

    return totalDistance; // 반환
}

void solve() {
    vector<int> indices(chickens.size(), 0);
    fill(indices.end() - m, indices.end(), 1); // 백터의 마지막 요소 m개를 1로 초기화. 오름차순으로 만들어 준 것
    int minChickenDistance = INT_MAX;

    do {
        vector<pair<int, int>> selectedChickens; // 치킨집 조합 만들기
        for (int i = 0; i < indices.size(); i++) {
            if (indices[i] == 1) {
                selectedChickens.push_back(chickens[i]);
            }
        }
        minChickenDistance = min(minChickenDistance, calculateChickenDistance(selectedChickens)); // 만든 치킨집 조합의 최소 도시 치킨 거리들 중 최소값
    } while (next_permutation(indices.begin(), indices.end())); 
    // 주어진 배열을 다음 순열로 변환하여 치킨집의 조합 생성. 
    // 주어진 시퀸스가 마지막 순열이라면, false 반환. 아니라면 다음 순열로 변환하여 true 반환. 

    cout << minChickenDistance << endl;
}

int main() {
    // 입력
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    map.resize(n, vector<int>(n));

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

    // 로직
    solve();

    return 0;
}