백준 c++ - 치킨 배달 (브루트포스 알고리즘)

 

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

15686번: 치킨 배달

 

1. 치킨 집 좌표를 담을 배열, 집 좌표를 담을 배열, m 개수만큼 치킨 집 좌표를 담을 배열

 - chicken, house, temp 순

 

 

2. chickenLove() 함수를 통해 temp에 치킨 집 좌표를 m개 만큼 삽입

 - 백준 연구소 문제도 풀면서 느꼈지만 chickenLove() 함수와 같이 비교 대상을 구하는 것이 중요하다고 느낌

 

3. distance() 함수를 통해 모든 집에서부터 temp에 담긴 치킨 집과 최소 거리를 구함

 

 

4. 출력

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
vector<pair<int, int>> temp;
int n, m, t, dist, result = 0x7fffffff;

int distance() // -> 집과 치킨집 최소 거리 구하는 함수
{
	int cal = 0;
	dist = 0;

	for (int i = 0; i < (int)house.size(); i++)
	{
		cal = 1000000;
		for (int j = 0; j < (int)temp.size(); j++)
		{
			cal = min(cal, abs(house[i].first - temp[j].first) + abs(house[i].second - temp[j].second));
		}

		dist += cal;
	}
	return dist;
}


void chickenLove(int idx, int cnt) // 치킨 집 좌표 temp 배열에 삽입 후 m과 같으면 거리 계산 시작
{

	if (cnt >= m)
	{
		int t4 = distance();
		result = min(t4, result);
		return;
	}

	for (int i = idx; i < (int)chicken.size(); i++)
	{
		temp.push_back(chicken[i]);

		// 현재 가리키고있는 i에서 + 1, 치킨집 개수 + 1
		chickenLove(i + 1, cnt + 1);
		temp.pop_back();
	}
}


int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", &t);
			if (t == 2) chicken.push_back({ i, j });
			else if (t == 1) house.push_back({ i, j });
		}
	}

	chickenLove(0, 0);
	printf("%d", result);
	return 0;
}