BOJ15686: 치킨 배달

작성일

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

  • 연휴동안 100문제 풀기 (7/100)
  • 백트래킹 문제. 걍 시키는 대로 풀면 됨. 입력되는 공간 이 매우 작다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

struct Point { int x,y; };
inline int abs(int n) { return n > 0 ? n : -n; }

int calc(vector<Point>& house, vector<Point>& selected) {
  int ans = 0;
  for(auto& p1: house) {
    int dist = INT_MAX;
    for(auto& p2: selected)
      dist = min(dist, abs(p1.x-p2.x) + abs(p1.y-p2.y));
    ans += dist;
  }
  return ans;
}

int combination(vector<Point>& house, vector<Point>& candi, vector<Point>& selected, int M, int m, int s) {
  if(M == m) return calc(house, selected);

  int ans = INT_MAX;
  for(int i = s; i < candi.size(); i++) {
    selected.push_back(candi[i]);
    ans = min(ans, combination(house, candi, selected, M, m+1, i+1));
    selected.pop_back();
  }
  return ans;
}

int main() {
  int N, M;
  vector<Point> house, candi, selected;
  cin >> N >> M;
  for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) {
    int tmp;
    cin >> tmp;
    if(tmp == 1) house.push_back({i,j});
    if(tmp == 2) candi.push_back({i,j});
  }
  cout << combination(house, candi, selected, M, 0, 0);
}