[BOJ] 15686 : 치킨배달

1. 문제

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

2. 접근법

먼저 치킨집 중 M개를 선택하고 최소 치킨 거리를 구하는 문제이다.
치킨집을 선택하는 방법이 핵심인것같다.

처음에 계속 시간초과가 났는데, 자신이 선택한 인덱스 이후에서 다음 치킨집을 선택하도록 코드를 변경한 후 해결할 수 있었다.

// 0: 빈칸, 1: 집, 2: 치킨집
 
#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
int chicken_index = 0;
int home_index = 0;
int origin_map[52][52] = { 0 };
int map[52][52] = { 0 };
int final_d = 987654321;
pair<int, int> chicken[14];
pair<int, int> selected[14];
vector<pair<int, int>> home;
bool visited[14] = {false};
 
int abs(int a) {
    return a>0 ? a : -1 * a;
}
 
int distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
 
 
 
int solve() {
    
    int total_d = 0;
    
    for (int i = 0;i < home.size();i++) {
        int min_d = 987654321;
        for (int k = 0; k < m; k++) {
            int d = distance(home[i].first, home[i].second, selected[k].first, selected[k].second);
            min_d = min_d > d ? d : min_d;
        }
        total_d += min_d;
    }
    
    /*
     for (int i = 1;i <= n;i++) {
     for (int j = 1;j <= n;j++) {
     if (map[i][j] != 1)continue;
     
     int min_d = 987654321;
     for (int k = 0;k<m;k++) {
     int d = distance(i, j, selected[k].first, selected[k].second);
     min_d = min_d > d ? d : min_d;
     }
     total_d += min_d;
     }
     }*/
    
    return total_d;
}
 
void select(int len, int k) {
    if (len == m) {
        int d = solve();
        final_d = final_d > d ? d : final_d;
        return;
    }
    for (int i = k;i<chicken_index;i++) {
        
            selected[len] = chicken[i];
            select(len + 1, i+1);
        
        
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2) {//치킨집 위치 저장
                chicken[chicken_index] = make_pair(i, j);
                chicken_index++;
            }
            else if (map[i][j] == 1) {//집 위치 저장
                home.push_back({i,j});
            }
        }
    }
    
    select(0,0);
    
    printf("%d\n", final_d);
    
    return 0;
}