백준 15686 치킨 배달 c++ [컴공과고씨]

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

15686번: 치킨 배달

 

문제 간단 정리

N x N 도시에 집과 치킨집이 있음.

한 집과 치킨 집의 거리는 | 집의 행 - 치킨집의 행 | + | 열 - 열 |  이런식으로 계산됨.

각 집과 가장 가까운 치킨 집 사이의 거리를 모두 합한 거리를 도시의 치킨 거리라고 한다.

문제에 M이 주어지는데 M개 만큼 치킨 집을 폐업했을 때 도시의 치킨 거리 가장 작게 되는 도시의 치킨 거리를 구하시오.

 

문제 해결 방법

간단하게 생각하면 주어진 개수 만큼 치킨 집을 없애고 도시의 치킨 거리를 구하면 된다.

여기서 중요한 것은 어떤 치킨 집을 폐업할 것인가가 핵심이 된다.

만약 1,2,3,4,5 치킨 집이 있고 이 중 2개를 폐업한다고 할 때 중복 없이 폐업하는 경우의 수는

1,2,3 | 1,2,4 | 1,2,5 | 1,3,4 | 1,3,5 | 1,4,5 | 2,3,4 | 2,4,5 | .... 쭉 갈 것이다.

이것을 우리는 조합이라고 한다.  n개 중 r개를 뽑는 것이기 때문에.

*이 순열에 관한 문제는 백준에 n과 m 시리즈 문제를 풀면 도움이 될 것이다.

조합을 구현하기 위해 재귀 함수를 통해 구현했다.

 

조합 구현 방식 

void combination(int cnt, int next){
    if(cnt == m){ // 순열이 다 찬 경우
        int temp = 0; // 도시의 치킨 거리
        for (int i = 0; i < idx2; i++){
            int mndis = 987654321; // 각 집과 가까운 치킨 집 사이의 거리
            // 도시의 치킨 거리
            for (int j = 0; j < m; j++){
                // 각 집과 가까운 치킨 집 사이의 거리
                 int dis= abs(hx[i] - bbqx[permu[j]]) + abs(hy[i] - bbqy[permu[j]]);
                if(mndis > dis)
                    mndis = dis; // 가장 가까운 치킨집 거리
            }
            temp += mndis;  
        }
        if(result > temp) // 최단의 도시의 치킨 거리일 경우
            result = temp;
    }else{
        // 조합 
        for (int i = next; i < idx; i++){
            permu[cnt] = i;
            combination(cnt + 1, i + 1);
        }
    }
}

else 부분이 핵심이라고 볼 수 있다.

우리는 permu[] 배열에 원하는 개수 m만큼 숫자를 채울 것이다. 여기서 숫자는 치킨 집 번호가 될 것이다.

0번 치킨 집, 1번 치킨 집 ......

1,2,3 | 1,2,4 | .... 이런식으로 그러기 위해서 cnt라는 변수를 두어서 permu 배열의 원소가 몇 개인지 세주고 

next 같은 경우는 1,2,2 같은 불가능 한 경우 혹은 1,2,3 | 1,3,2 처럼 같은 경우의 수를 제외하기 위해 사용해준다.

cnt == m 즉 원하는 개수 만큼 permu 배열에 원소를 채웠을 때 여기에 있는 치킨 집 번호를 가지고 도시의 치킨 거리를 구해주면 된다.

 

전체 코드

#include <iostream>
#include <cmath>
using namespace std;
int n, m;
int bbqx[15]; // 치킨 집의 x 좌표
int bbqy[15]; // 치킨 집의 y 좌표
int hx[2520]; // 집의 x 좌표
int hy[2520]; // 집의 y 좌표 
int permu[15]; // 순열 배열
int idx = 0; // 치킨 집의 개수
int idx2 = 0; // 집의 개수 
int result = 987654321; // 도시의 치킨 거리
 
void combination(int cnt, int next){
    if(cnt == m){ // 순열이 다 찬 경우
        int temp = 0; // 도시의 치킨 거리
        for (int i = 0; i < idx2; i++){
            int mndis = 987654321; // 각 집과 가까운 치킨 집 사이의 거리
            // 도시의 치킨 거리
            for (int j = 0; j < m; j++){
                // 각 집과 가까운 치킨 집 사이의 거리
                 int dis= abs(hx[i] - bbqx[permu[j]]) + abs(hy[i] - bbqy[permu[j]]);
                if(mndis > dis)
                    mndis = dis; // 가장 가까운 치킨집 거리
            }
            temp += mndis;  
        }
        if(result > temp) // 최단의 도시의 치킨 거리일 경우
            result = temp;
    }else{
        // 조합 
        for (int i = next; i < idx; i++){
            permu[cnt] = i;
            combination(cnt + 1, i + 1);
        }
    }
}
 
int main(){
    cin >> n >> m;
    int a;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> a;
            if(a == 2){
                bbqx[idx] = i;
                bbqy[idx] = j;
                idx++;
            }
            else if(a == 1){
                hx[idx2] = i;
                hy[idx2] = j;
                idx2++;
            }
        }
    }
    combination(0, 0);
    cout << result << '\n'; 
    return 0;
}