백준 / 15686번 / 치킨 배달 / C++

# 출처 : https://www.acmicpc.net/problem/15686

DFS 와 백트래킹만 적절하게 사용하면 되는 문제인데, 괜히 어렵게 풀다가 오래끌은 문제이다.

처음 풀이는 DFS로 depth가 치킨집의 개수 M과 같아지면 BFS로 전체 거리를 조사하는식으로 들어갔는데 시간초과나서 생각해보니..

전혀 그럴필요 없이 필요한 거리만 뽑아내면 됐었다. 

# 풀이

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define endl '\n';
using namespace std;
int N, M, ans = 1e9;
int map[55][18];
vector<pair<int, int>> homeV, chicBaseV, chicTargetV;
 
bool inRange(int r, int c)
{
    return (r >= 1 && r <= N) && (c >= 1 && c <= N);
}
int checking()
{
    int ret = 0;
    for (int i = 0; i < homeV.size(); ++i)
    {
        int tmp = 1e9;
        for (int j = 0; j < chicTargetV.size(); ++j)
            tmp = min(tmp, abs(homeV[i].first - chicTargetV[j].first) + abs(homeV[i].second - chicTargetV[j].second));
        ret += tmp;
    }
    return ret;
}
void DFS(int x, int depth)
{
    if (depth >= M)
    {
        int tmp = checking();
        if(ans > tmp)
            ans = tmp;
        return;
    }
    for (int i = x; i < chicBaseV.size(); ++i)
    {
        chicTargetV.push_back(chicBaseV[i]);
        DFS(i + 1, depth + 1);
        chicTargetV.pop_back();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
 
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
        {
            cin >> map[i][j];
            if (map[i][j] == 1)
                homeV.push_back({ i, j });
            else if (map[i][j] == 2)
                chicBaseV.push_back({ i, j });
        }
    DFS(0, 0);
    cout << ans << endl;
    return 0;
}