[백준] 15686번 치킨 배달 (C++, 삼성 기출)

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

기존에 풀던 문제들은 순열이라 순열방식으로 풀었다가 시간초과가 났다.
문제를 다시 잘 읽어보니 순서가 상관이 없었고, 조합 방식으로 해결했다.

void solve(int idx, int depth, vector<int>& pick) {
	// 최대 개수를 골랐을 때, 거리 계산
	if (pick.size() == m){
		answer = min(answer, get_chicken_distance(pick));
		return;
	}
	// 끝까지 탐색했으면 return
	if (depth == chicken.size()) return;
	vector<int> cp;
	// pick배열 복사
	for (int i = 0; i < pick.size(); i++) cp.push_back(pick[i]);
	cp.push_back(idx);
	// 선택한 것과 선택 안한 것 두개로 나눠서 호출
	solve(idx + 1, depth + 1, cp);
	solve(idx + 1, depth + 1, pick);
}

위의 코드가 메인 코드이다.
치킨집의 좌표를 저장하고 있는 vector를 돌면서 치킨집을 선택하는 경우와 안하는 경우만 처리해주면 모든 경우를 처리해줄 수 있다.

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
struct p {
public :
	int x; 
	int y;
	p(int x, int y) {
		this->x = x;
		this->y = y;
	}
};
vector<p> house;
vector<p> chicken;
int answer = 987654321;


// 거리 계산
int distance(p a, p b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}

// 모든 집에 대해서 
// 치킨 거리 계산
int get_chicken_distance(vector<int>& pick) {
	int sum = 0;
	for (int i = 0; i < house.size(); i++) {
		int min_distance = 987654321;
		for (int j = 0; j < pick.size(); j++) {
			min_distance = min(min_distance, distance(chicken[pick[j]], house[i]));
		}
		sum += min_distance;
	}
	return sum;
}


void solve(int idx, int depth, vector<int>& pick) {
	// 최대 개수를 골랐을 때, 거리 계산
	if (pick.size() == m){
		answer = min(answer, get_chicken_distance(pick));
		return;
	}
	// 끝까지 탐색했으면 return
	if (depth == chicken.size()) return;
	vector<int> cp;
	// pick배열 복사
	for (int i = 0; i < pick.size(); i++) cp.push_back(pick[i]);
	cp.push_back(idx);
	// 선택한 것과 선택 안한 것 두개로 나눠서 호출
	solve(idx + 1, depth + 1, cp);
	solve(idx + 1, depth + 1, pick);
}

int main() {
	ios_base::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++) {
			int in;
			cin >> in;
			if (in == 1) house.push_back(p(j, i));
			else if (in == 2) chicken.push_back(p(j, i));
		}
	}

	vector<int> pick;
	solve(0, 0, pick);
	cout << answer;
}