CS/알고리즘

백준 15686번: 치킨 배달

신정훈 2024. 2. 20. 02:00

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

문제 접근

 

완전 탐색 + 접근 문제이다.

 

입력값으로 주어지는 M개의 치킨 집을 골라야 한다.

 

치킨 거리 = 집에서 가장 가까운 치킨 집의 거리

도시의 치킨 거리 = 치킨거리의 합

 

M개의 치킨집을 조합한뒤

조합과 집의 좌표를 비교해 

가장 가장 가까운 치킨 집을 찾는다.

 

각집의 치킨 거리를 모두 더해

도시의 치킨 거리를 구한다.

 

각 조합에 대한 도시의 치킨 거리를 비교해

가장 작은 값을 구한다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <cstring>
#include <stack>

using namespace std;
int N, M;
int arr[51][51] = {};
vector<vector<int>> chickenList;
vector<pair<int, int>> chickenPos;
vector<pair<int, int>> housePos;

void combi(int start, vector<int> v)
{
	if (v.size() == M)
	{
		chickenList.push_back(v);
		return;
	}
	for (int i = start + 1; i < chickenPos.size(); i++)
	{
		v.push_back(i);
		combi(i, v);
		v.pop_back();
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.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)
				housePos.push_back({ i,j });
			if (arr[i][j] == 2)
				chickenPos.push_back({ i,j });
		}
	}
	int ans = 1e9;
	vector<int> v;
	combi(-1, v);
	for (int i = 0; i < chickenList.size(); i++)
	{
		// 도시의 치킨 거리 = 치킨 거리들의 합
		int ret = 0;
		for (int j = 0; j < housePos.size(); j++)
		{
			// 치킨 거리 = 집과 가장 가까운 치킨집과의 거리
			int mn = 1e9;
			for (auto ch : chickenList[i])
			{
				int dist = abs(housePos[j].first - chickenPos[ch].first) + abs(housePos[j].second - chickenPos[ch].second);
			    mn = min(mn, dist);
			}
			ret += mn;
		}
		ans = min(ans, ret);
	}

	cout << ans;
}