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;
}

✓ for 문과 재귀를 이용하여 조합을 만들 수 있다.

#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 (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;
    }
    for (int i=idx; i<(int)chicken.size(); i++) {
        v.push_back(i);
        solve(i+1, cnt+1);
        v.pop_back();
    }
}

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)

참고

• 백준 온라인 저지 : BOJ 15686