[백준] 15686번 치킨 배달

문제

https://www.acmicpc.net/problem/15686

풀이과정

Dfs와 백트래킹을 통한 완전탐색으로 구현을 했습니다.

M개의 치킨집을 골랐을 경우 최소거리의 합을 구하고 가장 작은 경우만 저장해서 출력했습니다.

DFS와 백트래킹을 통한 완전탐색 문제를 풀어봤다면 푸실 수 있을 것 같습니다.

알고리즘

1(집), 2(치킨집) 일 경우 각각 person, chicken 벡터에 위치를 저장합니다.
재귀함수를 통해 M개의 치킨집을 선택합니다
person 벡터를 돌며 집과 선택된 치킨집의 거리 중 최소값만을 더합니다.
치킨집 M개를 뽑는 모든 경우를 탐색하고 최소거리의 합 중 가장 작은 값만 저장합니다.

소스코드

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

using namespace std;

#define MAX_N 51
#define MAX_M 14
#define MAX_INF 987654321

int N, M, ans;
int city[MAX_N][MAX_N];
bool isused[MAX_M];

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

void Dfs(int cur_num, int cur_cnt)
{
    if (cur_num > chicken.size()) return;

    // M개의 치킨집이 정해지면 종료
    if (cur_cnt == M)
    {
        int cmp = 0;

        for (int i = 0; i < person.size(); i++)
        {
            int dist = MAX_INF;
            for (int j = 0; j < chicken.size(); j++)
            {
                if (isused[j])
                {
                    int px = person[i].first, py = person[i].second;
                    int samx = chicken[j].first, samy = chicken[j].second;
                    int d = abs(px - samx) + abs(py - samy);
                    dist = min(dist, d);
                }
            }
            cmp += dist;
        }

        ans = min(ans, cmp);

        return;
    }

    // 현재 치킨집을 사용할 경우
    isused[cur_num] = true;
    Dfs(cur_num + 1, cur_cnt + 1);
    // 사용하지 않는 경우
    isused[cur_num] = false;
    Dfs(cur_num + 1, cur_cnt);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> city[i][j];
            if (city[i][j] == 1)
                person.push_back(make_pair(i, j));
            else if (city[i][j] == 2)
                chicken.push_back(make_pair(i, j));
        }
    }

    ans = MAX_INF;

    Dfs(0, 0);

    cout << ans << "\n";

    return 0;
}