BOJ 15686 · 치킨 배달

알고리즘 분류 : 브루트 포스

집과 치킨집과의 거리를 각각 구해서 최소의 치킨 거리를 구하는 문제다. 여러 개의 치킨 집에서 M개의 치킨 집을 고른 후, 문제에 주어진 조건대로 치킨 거리를 구해서 답을 찾아야 한다.

입력받을 때, 치킨집(2)의 개수와 집(1)의 개수를 세고, 각 좌표 (X, Y)를 리스트에 저장한다.
치킨집의 총 개수를 K개라고 할 때, 재귀 함수를 통해 K개 중 M개를 골라야 한다. 조합 방식으로 고르면 된다.
M개의 치킨집을 모두 고르면, 집과 치킨집과의 치킨거리를 구하고, 그중 최솟값을 정답으로 한다.

C++ 소스코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct pos {
    int x, y;
};

int n, m, ans=1e9;
vector<pos> home, chicken;
vector<int> v;

void solve(int idx, int cnt) {
    if (idx > (int)chicken.size()) return;
    if (cnt == m) {
        int sum = 0;
        for (int i=0; i<(int)home.size(); i++) {
            int d = 1e9;
            for (auto j : v) {
                d = min(d, abs(home[i].x-chicken[j].x)+abs(home[i].y-chicken[j].y));
            }
            sum += d;
        }
        ans = min(ans, sum);
        return;
    }
    v.push_back(idx);
    solve(idx+1, cnt+1);
    v.pop_back();
    solve(idx+1, cnt);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            int a;
            scanf("%d", &a);
            if (a == 1) home.push_back({i, j});
            else if (a == 2) chicken.push_back({i, j});
        }
    }
    solve(0, 0);
    printf("%d\n", ans);
    return 0;
}

Python 3 소스코드

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
home, chicken, v = [], [], []
ans = 1e9

def solve(idx, cnt):
    global ans
    if idx > len(chicken):
        return
    if cnt == m:
        s = 0
        for hx, hy in home:
            d = 1e9
            for j in v:
                cx, cy = chicken[j]
                d = min(d, abs(hx-cx)+abs(hy-cy))
            s += d
        ans = min(ans, s)
        return
    v.append(idx)
    solve(idx+1, cnt+1)
    v.pop()
    solve(idx+1, cnt)

for i in range(n):
    for j in range(n):
        if a[i][j] == 1:
            home.append((i+1, j+1))
        elif a[i][j] == 2:
            chicken.append((i+1, j+1))
solve(0, 0)
print(ans)

✓ 파이썬은 itertools의 combinations를 이용하여, 조합(Combination) 방법으로 풀 수 있다.

✓ 소스코드 보기

from itertools import combinations
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
home, chicken = [], []
ans = 1e9
for i in range(n):
    for j in range(n):
        if a[i][j] == 1:
            home.append((i+1, j+1))
        elif a[i][j] == 2:
            chicken.append((i+1, j+1))
for k in combinations(chicken, m):
    s = 0
    for hx, hy in home:
        d = 1e9
        for cx, cy in k:
            d = min(d, abs(hx-cx)+abs(hy-cy))
        s += d
    ans = min(ans, s)
print(ans)