백준 15686 치킨 배달

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

서론

재귀를 이용한 완전탐색문제.

 

---

아이디어

2차원 배열을 만들지는 않고, 지도를 입력받을때 1이면 집 벡터에 좌표를 넣어주고 2면 치킨 벡터에 좌표를 넣어준다.

 

도시에 있는 치킨집 중 최대 M개를 골라서 가장 작은 도시의 치킨거리를 구해야하는데, 최대M개를 고르라고 해서 M개를 고르는 경우의 수, M-1을 고르는 경우의 수, M-2를 고르는 경우의 수 ....를 고려할 필요는 없이 M개를 고르는 경우의 수만 고려하면 된다. 치킨집이 M-1에 비해 M개면 수익이 감소할지는 모르나 우리는 치킨거리만 고려하면 되고, 치킨거리는 치킨집이 많을수록 당연히 작다.

그래서 도시에 있는 총 치킨집 중 M개를 골라야 하는데, 고를 수 있는 모든 경우의 수를 얻기 위해 재귀를 이용한 완전탐색을 진행한다. 

 

만약 도시의 치킨집의 개수가 4, M이 2면

1번	2번	3번	4번
T	T	F	F
T	F	T	F
T	F	F	T
F	T	T	F
F	T	F	T
F	F	T	T

(T는 치킨집을 선택, F는 치킨집을 선택하지 않음)

 

총 6개의 경우의 수가 나오고 코드는

recursive(index, selectCount, select){

	if(select == true) 치킨집[index] = true
    
 	if(selectCount == M) 도시의 치킨거리 계산()

 	recursive(index+1, selectCount+1, true)
	recursive(index+1, selectCount, false)

}

 

index는 치킨집의 번호, selectCount는 치킨집을 선택한 개수, select는 이번 치킨집을 선택했을 때이며 

위와 같은 방법으로 도시에 있는 치킨집 중 M개를 선택했다.

그리고 M개를 선택한 경우의 수 마다 도시의 치킨거리를 계산하고, 이 도시의 치킨거리들 중 최소값이 치킨집 중 어떤 M개를 선택했을때 도시의 치킨거리가 최소값이 나올 때이다.

 

도시의 치킨거리는

도시의 치킨거리 = 0

for(i=0;집 전체;i++){

	집 치킨거리 = 매우 큰 값
	for(j=0;치킨집 전체;j++) {
		if(치킨집[i] == 선택받았음) 집 치킨거리 = min(집 치킨거리, 집[i]와 치킨집[j] 거리 계산 값)
	}
	도시의 치킨거리 += 집 치킨거리
}

출력값 = min(출력값, 도시의 치킨거리) // selectCount가 M일때마다 갱신될 수 있음

 

---

구현

// c++

#include <algorithm>
#include <vector>
#include <iostream>

typedef struct st{
	int y;
	int x;
	bool select;
}st;

std::vector<st>house;
std::vector<st>chicken;
int n, m;
int result = 0x7f7f7f7f;

void input() {
	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int tmp;
			std::cin >> tmp;
			if (tmp == 1) house.push_back({ i, j, false });
			else if (tmp == 2)chicken.push_back({ i, j, false });
		}
	}
}

void rec(int idx, int selCnt, bool select) {
	if (idx != -1) chicken[idx].select = select;

	if (selCnt == m) {
		int dist = 0;
		for (int i = 0, hSize = house.size(); i < hSize; i++) {
			int tmpDist = 0x7f7f7f7f;
			for (int j = 0, cSize = chicken.size(); j < cSize; j++) {
				if (chicken[j].select == true) {
					tmpDist = std::min(tmpDist, abs(house[i].y - chicken[j].y) + abs(house[i].x - chicken[j].x));
				}
			}
			dist += tmpDist;
		}
		result = std::min(dist, result);
		return;
	}
	else if (idx == chicken.size() - 1) {
		return;
	}

	rec(idx + 1, selCnt + 1, true);
	rec(idx + 1, selCnt, false);

	return;
}

int main() {
	input();
	rec(-1, 0, false);
	std::cout << result;
}