백준 15686번 치킨 배달

문제

코드

cpp

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

using namespace std;

int n, m;

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

vector<vector<int>> c;
vector<int> cd;

int visit[13] = { 0, };
void combi(int d,int index)
{
    if (d == m)
    {
        c.push_back(cd);
        return;
    }

    for (int i = index; i < chicken.size(); i++)
    {
        if (visit[i] == 0)
        {
            visit[i] = 1;
            cd.push_back(i);
            combi(d + 1,i);
            cd.pop_back();
            visit[i] = 0;
        }
    }

}

int sub(int a, int b)
{
    if (a - b >= 0)
        return a - b;
    else
        return b - a;
}

int cau()
{
    int map[50][50] = { 0, };

    vector<int> answer;
    for (int i = 0; i < c.size(); i++)
    {
        vector<int> arr(house.size(), 100);
        for (int j = 0; j < c[i].size(); j++)
        {
            int index = c[i][j];
            int y = chicken[index].first;
            int x = chicken[index].second;

            for (int k = 0; k < house.size(); k++)
            {
                int y2 = house[k].first;
                int x2 = house[k].second;

                arr[k] = min(arr[k], sub(y, y2) + sub(x, x2));
            }
        }
        int sum = 0;
        for (auto i : arr)
            sum += i;

        answer.push_back(sum);
    }
    return *min_element(answer.begin(), answer.end());
}
int main()
{   
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int num;
            cin >> num;
            if (num == 1)
                house.push_back(make_pair(i, j));
            if (num == 2)
                chicken.push_back(make_pair(i, j));
        } 
    }
    combi(0, 0);
    
    cout << cau();
    
}

python

from itertools import combinations

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

home_list = []
chicken_list = []
board = []
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]

for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(n):
        if temp[j] == 1:
            home_list.append((i, j))
        elif temp[j] == 2:
            chicken_list.append((i, j))
    board.append(temp)


answer = 1e9

for i in list(combinations(chicken_list, m)):
    cnt = 0
    for hy, hx in home_list:
        dist = 1e9
        for cy, cx in i:
            dist = min(dist, abs(hy-cy)+abs(hx - cx))
        cnt += dist
    answer = min(answer, cnt)
print(answer)

풀이

문제에서는 N*N크기의 2차원 배열에 집과 치킨집의 정보를 담아서 입력값으로 줍니다. 이 때 사정상 M개의 치킨집이 문을 닫아야 한다고 가정했을 때 치킨거리가 최소가 되는 값을 출력하면 됩니다.
재귀 함수를 사용해서 모든 경우의 수를 구하고 나머지는 문제의 조건에 따라서 완전탐색으로 모든 경우의 수를 탐색하면 풀리는 문제입니다