백준 15686 (치킨 배달)

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

15686번: 치킨 배달

해당 문제는 집과 치킨 가게의 위치가 주어지고 M개의 가게만 남겼을 때 구할 수 있는 집들의 치긴 가게와의 거리중 최소 값을 구하는 문제이다.

풀이

1. 주어진 map을 탐색하며 집과 치킨 가게에 해당하는 좌표를 각각 배열 house, chekenList에 담는다.

2. 재귀 (조합) 을 사용하여 1개의 치킨 가게를 선택하며 계속 재귀를 수행하며 이때 남겨야 하는 가게의 수 m과 재귀의 회수가 일치할 때 각 집의 개수마다 재귀때 마다 선택한 치킨 가게의 좌표를 가지고오며 최소값을 갱신시켜며 문제를 풀면 된다.

#include <iostream>
#include <cstring>

using namespace std;
struct Node{
	int y, x;
};
int n;
int m;
int map[50][50];
int used[20];

int minn = 10000000;
vector<Node> house;
vector<Node> chekenList;

// 재귀 (조합)
void dfs(int level, int idx){
	if (level == m){
		int sum = 0;
		for (int i = 0; i < house.size(); ++i){
			int mn = 1000000;
			for (int j = 0; j < chekenList.size(); ++j){
				if (used[j] == 1){
					int cy = abs(house[i].y - chekenList[j].y);
					int cx = abs(house[i].x - chekenList[j].x);
					int res = cy + cx;
					if (res < mn) mn = res;
				}
			}
			sum += mn;
		}
		if (sum < minn) minn = sum;
		return;
	}
	for (int i = idx; i < chekenList.size(); ++i){
		int dy = chekenList[i].y;
		int dx = chekenList[i].x;
		used[i] = 1;
		dfs(level + 1, i + 1);
		used[i] = 0;
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	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){
            	// 치킨 가게 좌표 추가
				chekenList.push_back({ i, j });
			}
			if (map[i][j] == 1){
            	// 집 좌표 추가
				house.push_back({ i, j });
			}
		}
	}

	dfs(0, 0);
	printf("%d", minn);

}