백준[15686] - 치킨 배달

문제

백준 15686 문제 보기

접근 방법

모든 치킨 집과 주문하는 사람의 위치를 따로 저장한뒤 모든 치킨 집 조합에 대해서 주문 시키는 집의 거리 차를 최소로 하는 값을 출력하면 된다.

코드

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>

using namespace std;

int N, M, ans;
// 주문하는 사람
vector<pair<int, int>> applicant;
// 치킨 집 위치
vector<pair<int, int>> place;
int chk[50];
int map[51][51];

int dfs(int idx, int cnt) {
    // 범위 체크
    if(idx > place.size()) {
        return 0;
    }

    // 선택된 치킨 집의 갯수가 주어진 조건과 같을 때
    if(cnt == M) {
        int temp = 0;
        // 주문하는 집에서 가장 가까운 치킨집 위치를 찾아 dist에 저장
        for(int i = 0; i < applicant.size(); i ++) {
            int dist = 987654321;
            for(int j = 0; -1 != chk[j]; j ++) {
                int appR = applicant[i].first;
                int appC = applicant[i].second;
                int plR = place[chk[j]].first;
                int plC = place[chk[j]].second;

                dist = min(dist, abs(appR - plR) + abs(appC - plC));
            }
            temp += dist;
        }
        ans = min(ans, temp);
        return 0;
    }

    // idx번째 치킨 집에서 치킨 주문 O
    chk[cnt] = idx;
    dfs(idx + 1, cnt + 1);
    chk[cnt] = -1;

    // idx번째 치킨 집에서 치킨을 주문 X
    dfs(idx + 1, cnt);
    return 0;
}

int main() {

    cin >> N >> M;
    memset(chk, -1, sizeof(chk));
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> map[i][j];

            if(map[i][j] == 1) {
                applicant.push_back(make_pair(i, j));
            } else if(map[i][j] == 2) {
                place.push_back(make_pair(i, j));
            }
        }
    }

    ans = 987654321;
    dfs(0 , 0);

    cout << ans;
    return 0;
}