(C++) 백준 15686번 - 치킨 배달

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

15686번: 치킨 배달

풀이

Permutation을 사용하여 M개의 치킨집들의 조합을 뽑아내고 이에 대한 모든 집에서의 치킨 거리를 구한 후 모두 더함으로써 도시의 치킨 거리를 구하였다.

골드 문제치고 난이도가 어렵진 않다. 다만 Permutation을 사용하여 조합을 뽑아내는 방법에 익숙해질 필요가 있다고 느낀 문제였다.

#include <iostream>
#include <vector>
#include <algorithm>
#define X first 
#define Y second

using namespace std;

int city[52][52];
vector<pair<int, int> > house, chicken;
int n, m, total;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.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}); // 치킨집 저장
        }
    }

    vector<int> tmp(chicken.size(), 1); // 조합을 위한 임시 배열
    fill(tmp.begin(), tmp.begin() + chicken.size() - m, 0); // 앞의 치킨 집의 숫자 - m는 1,뒤의 m은 0

    int mn = 200000; // 최소값, 초기의 값은 집의 최대 수(100) * 치킨집의 최대 수(13) * 최대 거리(100)인 13000 이상으로 설정
    do{
        int chick_dist = 0; // 현재 치킨집 조합에서의 치킨 거리
        for(auto k: house){ // 전체 집에 대해 치킨 거리 계산
            int dist = 2000; // 현재 집에 대한 치킨 거리
            for(int i = 0; i < chicken.size(); i++){
                if(tmp[i] == 0) continue; // 이번 치킨집 조합에 속하지 않은 치킨집은 pass
                dist = min(dist, (abs(k.X - chicken[i].X) + abs(k.Y - chicken[i].Y))); // 과거 계산된 치킨 거리와 이번에 계산된 치킨 거리 중 최소값을 저장
            }
            chick_dist += dist; // 각 집마다의 치킨 거리 더하기
        }
        mn = min(mn, chick_dist); // 최소 도시 치킨 거리 갱신
    }while(next_permutation(tmp.begin(), tmp.end())); // 조합 계산
    cout << mn;
}