[BOJ/백준 15686][C++] 치킨 배달

문제

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

백준 15686

백준 15686

 

문제 내용

"치킨 거리"는 집과 가장 가까운 치킨집 사이의 거리이고, "도시의 치킨 거리"는 모든 집의 치킨 거리 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

 

크기가 N*N인 도시에 치킨집이 여러 개 있다. 이 중에 최대 M개만 남기고 나머지는 폐업시키려 한다.

이때 도시의 치킨 거리가 가장 작게 되는 경우를 구해야 한다.

 

문제 풀이

일단 도시의 치킨 거리가 가장 작게 되야 하기 때문에, 치킨집은 M개여야 한다. (치킨집이 많아야 각각의 집과의 거리도 줄어든다)

그럼 해당 문제는 아래의 과정으로 나눌 수 있다.

1. 전체 치킨집 중에 M개를 고른다. => 백트래킹 사용

2. 치킨 거리를 구한다. => 단순 구현

 

1. 전체 치킨집 중에 M개를 고른다.

void chooseChicken(int cnt, int cur) { // 중복 없이. 순서 상관 X (그래서 그냥 오름차순으로 함)
    if (cnt == m) {
        // 도시의 치킨 거리 계산 후 최솟값 업데이트
        resultMin = min(resultMin, calcDistanceOfCity());
        return;
    }

    for (int i = cur; i < originChicken.size(); i++) {
        resultChicken[cnt] = originChicken[i];
        chooseChicken(cnt + 1, i + 1);
    }
}

 

2. 치킨 거리를 구한다.

calcDistanceHouseAndChicken은 집과 치킨집 사이의 거리를 구하는 함수이다.

그리고 calcDistanceOfCity는 도시 전체의 치킨 거리를 구하는 함수이다.

calcDistanceOfCity에서, 각각의 집에 대한 치킨 거리를 구하기 위해, M개 선택해 둔 치킨집들과의 거리를 계산하며 min값을 갱신하면 된다.

vector<pair<int, int>> house; // 집들의 좌표
vector<pair<int, int>> resultChicken; // M개 고른 치킨집 좌표


// houseNum번째 집과 chickenNum번째 치킨집 사이의 거리 반환
int calcDistanceHouseAndChicken(int houseNum, int chickenNum) {
    int hr = house[houseNum].first;
    int hc = house[houseNum].second;
    int cr = resultChicken[chickenNum].first;
    int cc = resultChicken[chickenNum].second;

    return abs(hr - cr) + abs(hc - cc);
}

// 도시의 치킨 거리 구하기
int calcDistanceOfCity() {
    int ssum = 0;
    for (int i = 0; i < house.size(); i++) {
        int mmin = 1e5;
        for (int j = 0; j < resultChicken.size(); j++) {
            mmin = min(mmin, calcDistanceHouseAndChicken(i, j));
        }
        ssum += mmin;
    }
    return ssum;
}

 

코드

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int arr[51][51]; // 0 빈칸, 1 집, 2 치킨
vector<pair<int, int>> house;
vector<pair<int, int>> originChicken;
vector<pair<int, int>> resultChicken;
int resultMin = 1e5;

// houseNum번째 집과 chickenNum번째 치킨집 사이의 거리 반환
int calcDistanceHouseAndChicken(int houseNum, int chickenNum) {
    int hr = house[houseNum].first;
    int hc = house[houseNum].second;
    int cr = resultChicken[chickenNum].first;
    int cc = resultChicken[chickenNum].second;

    return abs(hr - cr) + abs(hc - cc);
}

// 도시의 치킨 거리 구하기
int calcDistanceOfCity() {
    int ssum = 0;
    for (int i = 0; i < house.size(); i++) {
        int mmin = 1e5;
        for (int j = 0; j < resultChicken.size(); j++) {
            mmin = min(mmin, calcDistanceHouseAndChicken(i, j));
        }
        ssum += mmin;
    }
    return ssum;
}

void chooseChicken(int cnt, int cur) { // 중복 없이. 순서 상관 X (그래서 그냥 오름차순으로 함)
    if (cnt == m) {
        // 도시의 치킨 거리 계산 후 최솟값 업데이트
        resultMin = min(resultMin, calcDistanceOfCity());
        return;
    }

    for (int i = cur; i < originChicken.size(); i++) {
        resultChicken[cnt] = originChicken[i];
        chooseChicken(cnt + 1, i + 1);
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                house.push_back({i, j});
            } else if (arr[i][j] == 2) {
                originChicken.push_back({i, j});
            }
        }
    }

    resultChicken.assign(m, {0, 0});
    chooseChicken(0, 0);

    cout << resultMin;
}