백준 15686번 치킨 배달 C/C++ 풀이

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

15686번: 치킨 배달

 

Brute Force 문제이다.

 

Brute Force란? 가능한 모든 조합를 구해서 답을 구하는 기법이다.

 

주어진 치킨집의 개수 중 m개에 해당하는 치킨집 조합을 모두 구한 후 그에 따른 거리 합의 최솟값을 구해주면 된다.

 

시간복잡도를 계산하기 위해 가장 worst case를 계산해보면

 

13개의 치킨집 중 6개를 선택하고 13!/7!6! 그 모든 조합에 집들(최대 100개)마다 최소 거리를 구해야하기 때문에 

 

(13C6)*6*100 = 1,029,600이 된다.

 

다행히 1억번보다 작기 때문에 시간 내에 여유롭게 풀이 가능하다.

 

#include <cstdio>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <utility>
#include <memory.h>
#include <vector>

using namespace std;

//INPUT이 클 경우 파일로 받는다.
FILE* in = fopen("input.txt", "r");

//문제에서 주어진 조건
#define N_MAX 50
#define M_MAX 13

int n, m;
int map[N_MAX][N_MAX];
int path[M_MAX];
int ans = INT_MAX;
vector<pair<int, int>> home, chicken;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

using namespace std;

//거리를 계산하는 함수
int calc_dis(int x, int y, int a, int b) {
	return abs(x - a) + abs(y - b);
}

//BRUTE FORCE를 위한 DFS
void dfs(int idx, int selected) {
	//M개의 조합이 완성되면 거리 최솟값의 합을 구한다.
	if (selected == m)
	{
		int ret = 0;
		for (int i = 0; i < home.size(); i++)
		{
			int x = home[i].first; int y = home[i].second;
			int tmp = calc_dis(x, y, chicken[path[0]].first, chicken[path[0]].second);
			for (int j = 1; j < m; j++)
			{
				tmp = min(tmp, calc_dis(x, y, chicken[path[j]].first, chicken[path[j]].second));
			}
			ret += tmp;
		}
        //기존의 거리 합보다 작을 경우 갱신
		if (ret < ans)
			ans = ret;
		return;
	}
    //모두 순회하면 종료
	if (idx == chicken.size())
		return;
    //경로를 표시하기 위한 배열
	path[selected] = idx;
	dfs(idx + 1, selected + 1);
	dfs(idx + 1, selected);
}



int main() {
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			fscanf(in, "%d", &map[i][j]);
	int idx = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
        	//값이 1일 경우 집 좌표로 PUSH
			if (map[i][j] == 1)
			{
				home.push_back(make_pair(i, j));
			}
            //값이 2일 경우 치킨 좌표로 PUSH
			else if (map[i][j] == 2)
			{
				chicken.push_back(make_pair(i, j));
			}
	dfs(0, 0);
	printf("%d", ans);
	return 0;
}