백준 15686 치킨 배달(c++)

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

15686번: 치킨 배달

<코드>

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

vector<pair<int,int>> house, chicken ,pick;
int n,m,t;
int ret = 100000000;
void dfs(int pos)
{
	if(pick.size()==m){
		int candi = 0;
		for(int i=0;i<house.size();i++){
			int min_dist = 1000000;
			for(int j=0;j<pick.size();j++){
				min_dist = min(min_dist,abs(house[i].second - pick[j].second) + abs(house[i].first - pick[j].first));
			}
			candi += min_dist;
		}
		if(ret>candi){
			ret = candi;
		}
		return;
	}
	
	for(int i=pos;i<chicken.size();i++)
	{
		pick.push_back(make_pair(chicken[i].first,chicken[i].second));
		dfs(i+1);
		pick.pop_back();
	}
}
int main()
{
	
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>t;
			if(t==1){
				house.push_back(make_pair(i,j));
			}
			if(t==2){
				chicken.push_back(make_pair(i,j));
			}
		}
	}
	
	dfs(0);
	
	cout<<ret<<'\n';
}

<풀이 과정>

이 문제는 dfs(깊이 우선 탐색)을 활용한 문제이다.

우선적으로 치킨과 집의 좌표를 push 해주고 가장 가까운 치킨집의 개수만큼 새로운 pair 벡터에 push 해주어야 한다. 

그 부분이 dfs함수안에 있는 for문이다. dfs는 재귀함수 기반으로 풀어나가는 방식이므로 처음에 chicken의 좌표를 새로운 pick 벡터에 push하고 dfs를 한번 재귀호출 시켜야 한다. 그리고 치킨의집의 개수가 m개가 되면 좌표간(house, chicken)의 거리가 최소가 되는 점들을 하나씩 더해주면 된다.