[백준] 15686번 치킨배달 (C++)

 

 

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

 

 

문제 설명

- 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리

- 도시의 치킨 거리 : 모든 집의 치킨 거리

치킨 집과 집의 위치가 주어질 때, m개의 치킨집을 선택해서 도시의 치킨 거리가 가장 작게 나오는 경우를 골라 출력하기

 

주요 로직

1. 최대 m개의 치킨집을 선택해야 한다.
- 조합을 이용해서 m개의 치킨집을 선택해서 vector<int> vList에다가 저장을 해두었다.

2. 치킨집과 집의 거리(치킨거리)를 구해서 다 더한 후, 가장 작은 값을 출력해야한다
- 집 한 곳과 m개의 치킨집 하나하나를 다 비교해서 최솟값을 구하도록 구현했다.

* 조합 코드 (void combi) 는 외워두기

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

// 0은 빈칸, 1은 집, 2는 치킨집 

int n,m;
int cnt = 987654321;
vector<vector<int>> vList;
int arr[53][53], visited[53][53];
vector<pair<int,int>> house, chicken; 

void combi(int idx, vector<int> v){
	if(v.size() == m){
		vList.push_back(v);
		return;
	}
	for(int i=idx+1; i<chicken.size(); i++){
		v.push_back(i);
		combi(i, v);
		v.pop_back();
	}
	return;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> arr[i][j];
			if(arr[i][j] == 1) house.push_back({i,j});
			else if(arr[i][j] == 2) chicken.push_back({i,j});
		}
	}
	
	vector<int> v;
	combi(-1,v);
	
	for(auto cList : vList){
		int ret = 0;
		for(auto it : house){
			int mn = 987654321;
			for(auto ch : cList)
				mn = min(mn, abs(it.first - chicken[ch].first) + abs(it.second - chicken[ch].second));
			ret += mn;
		}
		cnt = min(ret, cnt);
	}
	cout << cnt << "\n";
}