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

 

문제 링크 : https://www.acmicpc.net/problem/15686

 

단순한 브루트 포스 문제였습니다.

1. 입력받을 때 집과 치킨집 모두 vector로 저장합니다. (vector에 저장함으로써 위치를 모두 탐색하지 않아도 됩니다)
2. DFS로 m개를 고를 수 있는 모든 경우의 수를 구합니다.
3. DFS로 m개를 고를 때마다 치킨 거리를 계산하여 줍니다.
4. 치킨 거리 중 가장 작은 값이 정답입니다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, m;
int map[52][52];
vector<pair<int,int>> store;  //치킨집들 
vector<pair<int, int>> house;  //가정집들
vector<pair<int, int>> choice;  // m개 고른 치킨집들

int calc()  //m개를 고른경우 치킨거리 계산
{
	int sum = 0;
	for (int i = 0; i < house.size(); i++)
	{
		int house_x = house[i].first;
		int house_y = house[i].second;
		int minn = 987654321;
		for (int j = 0; j < choice.size(); j++)
		{
			int store_x = choice[j].first;
			int store_y = choice[j].second;
			minn = min(minn, abs(house_x - store_x) + abs(house_y -store_y));
		}
		sum += minn;
	}
	return sum;
}

int dfs(int start,int count)
{
	if (count == 0)              //m개를 모두 고른 경우
	{
		int total_distance = calc();
		return total_distance;
	}
	int minn = 987654321;
	for (int i = start; i < store.size(); i++) //start이후로부터만 선택하면 됨
	{
		choice.push_back(store[i]);
		minn=min(minn,dfs(i+1,count - 1));   
		choice.pop_back();
	}
	return minn;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 2)store.push_back(make_pair(i, j));
			else if (map[i][j] == 1)house.push_back(make_pair(i, j));
		}
	}

	int result=dfs(0,m);
	cout << result << "\n";

	return 0;
}

 

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.