문제

문제 링크

해설

• 두 가지 방법으로 풀 수 있습니다.
  • 조합( 헤더파일의 next_permutation() 함수)을 이용하는 방법
  • 재귀함수를 이용하는 방법

① 조합을 이용하는 방법

• 입력받은 데이터 중 치킨집의 개수를 chicken_cnt 라는 변수로 카운팅합니다.

• chicken_cnt 크기의 bool 타입 배열 except를 만든 뒤 모두 true로 초기화 합니다.

• 선택할 최대 M개의 치킨집 개수만큼 앞에서부터 false로 초기화합니다.

  • 대략 {false, false, true, true, ...} 이런 형태의 배열이 만들어집니다.
  • 중요한 점은, 최대 M개의 치킨집을 고를 때 최소 치킨거리를 구하기 위해서는 항상 M개를 골라야 한다는 점입니다.
  • 치킨집이 많으면 많을수록 치킨거리가 짧아질 가능성은 당연히 높아지겠죠?

• 이 배열에 대해 next_permutation() 함수를 돌리면, 순열 대신 ‘조합’을 구할 수 있습니다.

• 배열 except의 i번째 요소가 false일 때, 대응하는 i번째 치킨집이 ‘선택됨’을 의미합니다.

• 각 집에 대해 선택된 치킨집을 대상으로 치킨거리를 모두 구합니다.

• 그 중 가장 짧은 치킨거리를 구하고, 그 거리들의 합을 구하면 이번 경우의 수의 해당 도시의 치킨거리를 성공적으로 구한 것이 됩니다.

• 다시 강조드리지만, 조합을 사용할 수 있었던 이유는 이 문제에서 요구하는 ‘최소 치킨거리’를 구하기 위해서는 ‘항상 M개 치킨집을 선택해야 함’을 쉽게 예측할 수 있기 때문입니다.

  • 만일, 이것을 보장할 수 없으며 0개부터 M개까지 치킨집 개수를 변경하며 선택해야 한다면 시간 내에 풀 수 있을지 모르겠네요.

② 재귀함수를 이용하는 방법

• 정석적인 풀이방법입니다.
• 입력받은 정보에 따라 모든 치킨집 좌표를 하나의 배열에 저장한 뒤
  • i번째 치킨집을 선택하는 경우
  • i번째 치킨집을 선택하지 않는 경우로 나눠 재귀를 돌립니다.

void foo(int cnt, int idx) {
    ...
    for (i = idx ~ chicken_cnt) {
        selected[cnt] = i;    // i번째 치킨집 선택
        foo(cnt + 1, i + 1);  // 재귀
    }
}

• 조금 더 이해하기 쉽게 의사코드로 나타내면 위와 같습니다.
• selected[] 배열에 선택한 0~M개의 치킨집 번호를 넣을 것입니다.
• i번째 치킨집을 선택하지 않는 경우는 i + 1번째 치킨집을 선택하는 경우에 덮어씌워지므로 따로 적지 않아도 괜찮습니다.

코드

① 조합을 이용하는 방법

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

int N, M;
int city[50][50];
int house_cnt, chicken_cnt, answer = 1e9;
pair<int, int> house[100], chicken[13];

inline int get_dist(int sy, int sx, int dy, int dx) {
    return (abs(sy - dy) + abs(sx - dx));
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> M;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            cin >> city[y][x];
            if (city[y][x] == 1)        house[house_cnt++]      = {y, x};
            else if (city[y][x] == 2)   chicken[chicken_cnt++]  = {y, x};
        }
    }
    vector<bool> except(chicken_cnt, true);
    for (int i = 0; i < M; i++) except[i] = false;

    do {
        int dist = 0;
        for (int i = 0; i < house_cnt; i++) {
            int dist_per_house = 1e9;
            for (int j = 0; j < chicken_cnt; j++) {
                if (except[j]) continue;
                dist_per_house = min(dist_per_house,
                                     get_dist(house[i].first, house[i].second,
                                              chicken[j].first, chicken[j].second));
            }
            dist += dist_per_house;
        }
        answer = min(answer, dist);
    } while (next_permutation(begin(except), end(except)));
    cout << answer << '\n';

    return 0;
}

소스코드 링크

② 재귀함수를 이용하는 방법

#include <iostream>
using namespace std;

int N, M, answer = 1e9;
int city[100][100];
pair<int, int> home[100], chick[13];
int home_cnt, chick_cnt, selected[13];

inline int get_dist (pair<int, int> s, pair<int, int> d) {
    return (abs(s.first - d.first) + abs(s.second - d.second));
}

void simulate(int cnt, int idx) {
    if (cnt == M) {
        int total_dist = 0;
        for (int i = 0; i < home_cnt; i++) {
            int home_dist = 1e9;
            for (int j = 0; j < M; j++)
                home_dist = min(home_dist, get_dist(home[i], chick[selected[j]]));
            total_dist += home_dist;
        }
        answer = min(answer, total_dist);
        return;
    }
    for (int i = idx; i < chick_cnt; i++) {
        selected[cnt] = i;
        simulate(cnt + 1, i + 1);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> M;
    for (int y = 0; y < N; y++)
        for (int x = 0; x < N; x++) {
            cin >> city[y][x];
            if (city[y][x] == 1) home[home_cnt++] = {y, x};
            else if (city[y][x] == 2) chick[chick_cnt++] = {y, x};
        }
    simulate(0, 0);
    cout << answer << '\n';
    return 0;
}

소스코드 링크

결과

• 재귀함수를 사용한 쪽이 조금 더 빠르게 나왔습니다.