15686 치킨배달

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

 

/*
0은 빈
1이 집
2가 치킨

치킨집 좌표를 1차원 벡터에 놓고
집도 동일하다.
경우의 수 - 조합

branch는 치킨집 모든 갯수.
depth 는 M개
depth가 M개 일 때 집과 치킨집 사이의 거리가 가장 작은 것을 선정하여
result 에 합산하고 Min값과 비교하여 가장 작은 값을 결과값으로 출력.

*/

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

struct point {
	int x;
	int y;
};
vector<point>home;
vector<point>restruant;
vector<point>pickedRestruant;
int N, M;
int diff(point h, point r) {
	return abs(h.x - r.x) + abs(h.y - r.y);
}
int resultMin = 10e7;
void combi(int lv, int m) {
	if (m == M) { // 폐업시키지 않을 집 M개일 떄
		int result = 0;
		for (const auto & h : home){
			int minDist = 10e7;
			for (const auto& r : pickedRestruant) {
				minDist = min(minDist, diff(h, r));
			}
			result += minDist;
		}

		resultMin = min(result, resultMin);
		return;
	}
	for (int idx = lv; idx < restruant.size(); ++idx) {
		pickedRestruant.push_back({ restruant[idx].x, restruant[idx].y });
		combi(idx + 1, m+1);
		pickedRestruant.pop_back();
	}
}

int main(void) {
	cin >> N >> M;
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < N; ++x) {
			int val;
			cin >> val;
			if (val == 1) //집
				home.push_back({ y,x });
			if (val == 2) { // 치킨
				restruant.push_back({ y,x });
			}
		}
	}
	combi(0, 0);
	cout << resultMin << endl;
}

풀이 설명 ( 못풀었다면 못푼이유 )

dfs 조합으로 풀이했다. 폐업시키지 않을 치킨 집 수에 대한 경우의 수를 전체 치킨 집 수에서 찾아서 해당 경우들 안에서 치킨거리 (집-치킨집 간 거리가 제일 작은 거리)들 합산하여 각 경우의 치킨거리 총합들을 비교하여 가장 작은 총합 거리를 구한다.

그런데, 시간초과가 왜 나는지 모르겠다. —> 치킨집을 2, 집을 1로 오해했던게 원인…