[알고리즘] 치킨 배달

포인트

1. 조합을 이용을 하여 m개 까지 치킨집을 구할 수 있는가?

조합을 구하는 건 보통 3가지가 있는 것 같다. 

- 순열을 활용하여 조합을 구성하는 방법

- 확인 배열을 만들고 조합을 구성하는 방버

- 선택, 비선택 원리를 이용하여 조합을 구하는 방법 (제일 직관적이라고 생각합니다.)

2. 재귀를 잘 할 수 있는가? 

<2021.03.07> 

- 파이썬으로도 도전을 해보자

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

재귀 조합을 이용하여 푸는 방법

// 본인이 조합을 구할 때 주로 쓰는 방법
#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

int n, m;
int map[51][51];

vector<pair<int, int>> house, chicken, sel;
vector<int> dists;


int distance() {
    int a = 0;
    for (auto ele1 : house) {
        int dist = 987654321;
        for (auto ele2 : sel) {
            int Dist = abs(ele2.first - ele1.first) + abs(ele2.second - ele1.second);
            dist = min(dist, Dist);
        }
        a += dist;
    }
    return a;
}

void go(int index, int cnt) {
    if (cnt == m) {
        dists.push_back(distance());
        return;
    }

    if (index >= chicken.size()) return;

    sel.push_back(chicken[index]);
    go(index + 1, cnt + 1);
    sel.pop_back();

    go(index + 1, cnt);
}


int main(void) {

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) house.push_back(make_pair(i, j));
            if (map[i][j] == 2) chicken.push_back(make_pair(i, j));
        }
    }

    go(0, 0);
    cout << *min_element(dists.begin(), dists.end()) << '\n';
    return 0;
}

 

순열을 이용하여 푸는 방법

#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;

int main() {
    cin >> n >> m;
    vector<vector<int>> map(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) house.push_back({i, j});
            if (map[i][j] == 2) chicken.push_back({i, j});
        }
    }
    vector<int> d(chicken.size());
    for (int i = 0; i < m; i++) {
        d[i] = 1;
    }
    sort(d.begin(), d.end()); // 순열은 항상 정렬
    int answer = 987654321;
    do {
        int a = 0;
        for (auto ele1 : house) {
            vector<int> dists;
            for (int i = 0; i < chicken.size(); i++) {
                if (d[i] == 0) continue;
                auto ele2 = chicken[i];
                dists.push_back(abs(ele1.first - ele2.first) + abs(ele1.second - ele2.second));
            }
            a += *min_element(dists.begin(), dists.end());
        }

        answer = min(answer, a);
    } while (next_permutation(d.begin(), d.end()));
    cout << answer << '\n';
    return 0;
}

 

재귀 순열을 이용하여 구하는 방법

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

int n, m, answer;
int map[50][50];
bool sel[13];

vector<pair<int, int>> house, chicken, vc;

int calcDistance() {
    int sum = 0;
    for (int i = 0; i < house.size(); i++) {
        int x, y;
        tie(x, y) = house[i];
        int d = 99999999;

        for (int j = 0; j < vc.size(); j++) {
            int xx, yy;
            tie(xx, yy) = vc[j];
            int dist = abs(xx - x) + abs(yy - y);

            d = min(d, dist);
        }
        sum += d;
    }
    return sum;
}

void go(int idx, int count) { //재귀 함수
    if (count == m) {
        answer = min(answer, calcDistance());
        return;
    }

    for (int i = idx; i < chicken.size(); i++) {
        if (sel[i] == true) continue;
        sel[i] = true;
        vc.push_back(chicken[i]);
        go(i, count + 1);
        sel[i] = false;
        vc.pop_back();
    }
}

int main() {
    answer = 99999999;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) house.push_back(make_pair(i, j));
            if (map[i][j] == 2) chicken.push_back(make_pair(i, j));
        }
    }
    go(0, 0);

    cout << answer << endl;
}

2021 03 07

n, m = map(int, input().split())

data = [list(map(int, input().split())) for _ in range(n)]

chicken = []
house = []
for i in range(n):
    for j in range(n):
        if data[i][j] == 2:
            chicken.append([i, j])
        if data[i][j] == 1:
            house.append([i, j])

distance = []
sel = []


def go(index: int, cnt: int):
    if cnt == m:
        a = 0
        for ele1, ele2 in house:
            dist = 987654321
            for ele3, ele4 in sel:
                dist = min(dist, abs(ele3 - ele1) + abs(ele4 - ele2))
            a += dist
        distance.append(a)
        return

    if index >= len(chicken):
        return

    sel.append(chicken[index])
    go(index + 1, cnt + 1)
    sel.pop()

    go(index + 1, cnt)


go(0, 0)
print(min(distance))