134. 치킨 배달

백준

from itertools import combinations
n, m = map(int, input().split())

#0은 빈 칸, 1은 집, 2는 치킨집
#r과 c는 1부터 시작
#치킨 거리는 집과 가장 가까운 치킨집 사이의 거리
#도시의 치킨 거리는 모든 집의 치킨 거리의 합
#임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|
board = [list(map(int, input().split())) for _ in range(n)]

house = []
chicken = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 1: house.append((i, j))
        elif board[i][j] == 2: chicken.append((i, j))
 
value = float('inf')
for ch in combinations(chicken, m):
    plus = 0
    for home in house:
        plus += min([abs(home[0]-i[0])+abs(home[1]-i[1]) for i in ch])
        if value <= plus: break
    if plus < value: value = plus
 
print(value)

from itertools import combinations

n, m = map(int, input().split())
chicken, house = [], []

for r in range(n):
    data = list(map(int, input().split()))
    for c in range(n):
        if data[c] == 1:
            house.append((r, c)) # 일반 집
        elif data[c] == 2:
            chicken.append((r, c)) # 치킨집

# 모든 치킨 집 중에서 m개의 치킨 집을 뽑는 조합 계산
candidates = list(combinations(chicken, m))

# 치킨 거리의 합을 계산하는 함수
def get_sum(candidate):
    result = 0
    # 모든 집에 대하여
    for hx, hy in house:
        # 가장 가까운 치킨 집을 찾기
        temp = 1e9
        for cx, cy in candidate:
            temp = min(temp, abs(hx - cx) + abs(hy - cy))
        # 가장 가까운 치킨 집까지의 거리를 더하기
        result += temp
    # 치킨 거리의 합 반환
    return result

# 치킨 거리의 합의 최소를 찾아 출력
result = 1e9
for candidate in candidates:
    result = min(result, get_sum(candidate))

print(result)

2. C++

#include <bits/stdc++.h>

using namespace std;

int n, m;
int arr[50][50];
vector<pair<int, int> > chicken;
vector<pair<int, int> > house;

// 치킨 거리의 합을 계산하는 함수
int getSum(vector<pair<int, int> > candidates) {
    int result = 0;
    // 모든 집에 대하여
    for (int i = 0; i < house.size(); i++) {
        int hx = house[i].first;
        int hy = house[i].second;
        // 가장 가까운 치킨 집을 찾기
        int temp = 1e9;
        for (int j = 0; j < candidates.size(); j++) {
            int cx = candidates[j].first;
            int cy = candidates[j].second;
            temp = min(temp, abs(hx - cx) + abs(hy - cy));
        }
        // 가장 가까운 치킨 집까지의 거리를 더하기
        result += temp;
    }
    // 치킨 거리의 합 반환
    return result;
} 

int main(void) {
    cin >> n >> m;

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            cin >> arr[r][c];
            if (arr[r][c] == 1) house.push_back({r, c}); // 일반 집
            else if (arr[r][c] == 2) chicken.push_back({r, c}); // 치킨집
        }
    }

    // 모든 치킨 집 중에서 m개의 치킨 집을 뽑는 조합 계산
    vector<bool> binary(chicken.size());
    fill(binary.end() - m, binary.end(), true);

    // 치킨 거리의 합의 최소를 찾아 출력
    int result = 1e9;

    do {
        vector<pair<int, int> > now;
        for (int i = 0; i < chicken.size(); i++) {
            if (binary[i]) {
                int cx = chicken[i].first;
                int cy = chicken[i].second;
                now.push_back({cx, cy});
            }
        }
        result = min(result, getSum(now));
    } while(next_permutation(binary.begin(), binary.end()));

    cout << result << '\n';
}