[DFS] 백준 15686 치킨집 배달 C++

유(YOO) 2023. 9. 14. 23:14

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

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m, answer;
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;
bool visited[14];

void dfs(int idx, int depth) {
    if (depth == m) {
        int total = 0;
        for(int i=0; i<home.size(); i++) { // 집과 치킨집 거리 계산
            int dist = 1e9;
            for(int j=0; j<chicken.size(); j++) {
                if (!visited[j]) continue;
                dist = min(dist, abs(home[i].first - chicken[j].first) + abs(home[i].second - chicken[j].second));
            }
            if (dist != 1e9) total += dist;
        }

        answer = min(answer, total);

        return;
    }

    for(int i=idx; i<chicken.size(); i++) { // 시간 초과 해결
        if (visited[i]) continue;
        visited[i] = true;
        dfs(i+1, depth+1);
        visited[i] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    int num;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> num;
            if (num == 2) chicken.push_back({i, j});
            else if (num == 1) home.push_back({i, j});
        }
    }

    answer = 1e9;
    dfs(0, 0);

    cout << answer;

    return 0;
}