[알고리즘 문제] 백준15686 - 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

치킨 가게중 M개를 선정하고 모두 선정했다면 각 집에서 치킨집과의 최단 거리를 구합니다. 여기서 M개의 가게를 선정할 때는 재귀를 사용하였고 선정한 가게는 visited[]에 체크해 주었습니다.

 

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

using namespace std;

const int MAX = 51;

vector<pair<int, int>> ck;
vector<pair<int, int>> homes;
vector<pair<int, int>> curCk;

int visited[13];
int ans = 987654321;
int s, M;

int dis(pair<int, int> p1, pair<int, int> p2)
{
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

void search(int index, int depth)
{
    if (depth == M)
    {
        int tmp1 = 0;
        for (int h = 0; h < homes.size(); h++)
        {
            int tmp2 = 987654321;
            for (int c = 0; c < ck.size(); c++)
            {
                if (visited[c])
                {
                    tmp2 = min(tmp2, dis(homes[h], ck[c]));
                }
            }
            tmp1 += tmp2;
        }
        ans = min(ans, tmp1);
        return;
    }
    if (index == ck.size())
    {
        return;
    }

    visited[index] = true;         
    search(index + 1, depth + 1); // index번째 가게를 선정

    visited[index] = false;
    search(index + 1, depth);    // index번째 가게 선정 x
}
int main()
{
    int map[MAX][MAX];
    cin >> s >> M;

    for (int y = 1; y <= s; y++)
    {
        for (int x = 1; x <= s; x++)
        {
            cin >> map[y][x];
            if (map[y][x] == 2)
            {
                ck.push_back({y, x});
            }
            else if (map[y][x] == 1)
            {
                homes.push_back({y, x});
            }
        }
    }

    search(0, 0);
    cout << ans;
    return 0;
}