백준 15686 치킨 배달 C++ 풀이

처음 이 문제를 봤을때는 당연히 BFS, DFS 문제일 것 같지만, 사실은 그렇지 않다. 이 문제에서 우리가 생각해야할 것은 단순히 x축 y축 좌표를 이용해서 거리를 계산해야하는 것이기에,

이미 건설되어 있는 치킨집 중에서 M개를 뽑고, 그 M개에 대한 House들의 최소거리를 구해서, 그 최소거리를 출력시켜주는 단순한 백트래킹 문제였던 것이다.

#include <iostream>
#include <vector>
using namespace std;
int N, M;
int vil[51][51] = {0};
vector<int> ans;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
int min1 = 999999;
void check1(int count, int last)
{

    if (count == M)
    {
        int imsi = 0;

        for (int i = 0; i < house.size(); i++)
        {
            int housesize = 999999;
            for (int j = 0; j < ans.size(); j++)
            {
                if ((abs(chicken[ans[j]].first - house[i].first) + abs(chicken[ans[j]].second - house[i].second)) < housesize)
                {
                    housesize = abs(chicken[ans[j]].first - house[i].first) + abs(chicken[ans[j]].second - house[i].second);
                }
            }
            imsi = imsi + housesize;
        }
        if (imsi < min1)
        {

            min1 = imsi;
        }
    }
    else
    {

        for (int i = last + 1; i < chicken.size(); i++)
        {
            ans.push_back(i);
            check1(count + 1, i);
            ans.pop_back();
        }
    }
}

int main()
{
    cin >> N >> M;

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

    check1(0, -1);
    cout << min1;
}

이렇게, 공간좌표를 생각할 필요 없이 단순한 백트래킹 코드가 나오게 된다!