[알고리즘] C++ 백준 15686 치킨 배달

백준 15686

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

15686번: 치킨 배달

 

풀이 전 나의 생각

이 문제를 처음 봤을 땐 BFS로 풀면 될 것이라고 생각했지만 생각을 정리하다 보니 결코 BFS로 풀면 안되는 문제였다.

만약 BFS로 진행하게 된다면 시간초과가 난다. 이유는 당연하게도 너무 많은 탐색을 진행하게 되기 때문이다.

또한 거리를 탐색할 수 있는 효율적인 계산식이 있는데 하나 씩 탐색하는 것은 굉장히 비효율 적이다.

 

그렇기 때문에 이 문제는 <DFS, 조합 + 최소값을 구하는 거리계산>을 이용하면 쉽게 풀 수 있다.

 

이 문제의 포인트는 집에서 치킨집 까지의 최소거리를 구하는 것이다.

그러면 우선 해야할 것은 모든 치킨집 중에서 m개의 치킨집을 선택 할 경우의 수를 모두 구해야 한다.  m개의 치킨집을 선택하는 모든 경우의 수를 구한다면 그 중에서 최소값만 뽑아내면 될 것이다.

 

다음으로 조합마다 최소거리를 구하는 과정을 거쳐야 한다.

 

1. 집 한 곳에서 선택한 치킨집을 순회하며 어떤 치킨집을 최소로 갈 수 있는지 거리를 계산해준다.

2. 순회가 끝났다면 계산이 끝난 최소거리를 임시 최종값에 넣어 준다.

3. 모든 집의 순회가 끝났다면 임시 최종값과 최종값의 최소값을 비교하여 값을 넣어준다.

 

이 과정을 조합마다 반복해주면 최소거리를 쉽게 구할 수 있다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;

int board[51][51];
int n, m = 0;
int res = INT_MAX;
vector<pair<int, int>> home;
vector<pair<int, int>> chiken;
vector<int> selected;

void get_dis()
{
	int get_res = 0;
	for (int i = 0; i < home.size(); i++)
	{
		int min_dis = INT_MAX;
		int dis = 0;
		for (int j = 0; j < selected.size(); j++)
		{
			dis = abs(home[i].first - chiken[selected[j]].first) + abs(home[i].second - chiken[selected[j]].second);
			min_dis = min(min_dis, dis);
		}
		get_res += min_dis;
	}
	res = min(res, get_res);
}

void select_chiken(int start, int cnt)
{
	if (cnt == m)
	{
		get_dis();
	}

	for (int i = start; i < chiken.size(); i++)
	{
		selected.push_back(i);
		select_chiken(i + 1, cnt + 1);
		selected.pop_back();
	}
}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 1)
			{
				home.push_back({i, j});
			}
			if (board[i][j] == 2)
			{
				chiken.push_back({i, j});
			}
		}
	}
	select_chiken(0, 0);
	
	cout << res;
}