백준 15686번 [치킨 배달](C++)-yes6686- 티스토리

백준 문제 풀이: 15686 [치킨 배달]

---

문제 링크: https://www.acmicpc.net/problem/15686

문제 설명:

도시의 치킨 거리를 최소화하기 위해 M개의 치킨집을 선택해야 합니다. 치킨 거리란 집과 가장 가까운 치킨집 사이의 거리를 의미하며, 도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다. 도시 크기는 NxN이며, 각 칸은 집(1), 치킨집(2), 빈 칸(0) 중 하나입니다.

입력:

• 첫째 줄에 자연수 N과 M이 주어집니다. (2 ≤ N ≤ 50, 1 ≤ M ≤ 13)
• 둘째 줄부터 N개의 줄에 도시의 정보가 주어집니다.

출력:

• 선택한 M개의 치킨집으로 도시의 치킨 거리의 최소값을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
vector<pair<int, int>> houses, chickens;
vector selected;
int min_distance = 1e9;

int calculate_chicken_distance() {
    int total_distance = 0;
    for (auto house : houses) {
        int hx = house.first, hy = house.second;
        int min_dist = 1e9;
        for (int i = 0; i < chickens.size(); i++) {
            if (selected[i]) {
                int cx = chickens[i].first, cy = chickens[i].second;
                min_dist = min(min_dist, abs(hx - cx) + abs(hy - cy));
            }
        }
        total_distance += min_dist;
    }
    return total_distance;
}

void dfs(int idx, int count) {
    if (count == m) {
        min_distance = min(min_distance, calculate_chicken_distance());
        return;
    }
    if (idx >= chickens.size()) return;

    selected[idx] = 1;
    dfs(idx + 1, count + 1);
    selected[idx] = 0;
    dfs(idx + 1, count);
}

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

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x == 1) houses.push_back({i, j});
            else if (x == 2) chickens.push_back({i, j});
        }
    }

    selected.resize(chickens.size(), 0);
    dfs(0, 0);
    cout << min_distance << '\n';
    return 0;
}

예제

입력:
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

출력:
5

---

코드 설명

• 입력 처리:
  • 치킨집과 집의 좌표를 각각 chickens와 houses에 저장합니다.
• DFS로 조합 생성:
  • DFS를 통해 치킨집의 M개 조합을 선택합니다.
  • 선택된 치킨집은 selected 배열로 표시됩니다.
• 도시 치킨 거리 계산:
  • 각 집마다 가장 가까운 선택된 치킨집과의 거리를 계산합니다.
  • 모든 집의 거리를 더하여 도시의 치킨 거리를 구합니다.

시간 복잡도

• 치킨집이 최대 13개이므로 조합의 개수는 O(2^13)입니다.
• 각 조합마다 도시 치킨 거리를 계산하는 데 O(N^2)입니다.
• 최대 시간 복잡도는 O(2^13 × N^2)이며, N이 최대 50일 때 충분히 해결 가능합니다.

---

결과

코드는 도시의 치킨 거리를 최소화하는 M개의 치킨집을 정확히 선택하며, DFS를 활용한 최적화된 탐색으로 효율적으로 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!