15656 치킨배달

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

15686번: 치킨 배달

골드 5

 

#include <stdio.h>
#include <vector>
#include <algorithm>
#define INF 0x7fffffff

using namespace std;

struct POSI {
	int y, x;
};

int n, m, type, answer;

vector <POSI> house, shop, pick;

// 조합
void DFS(int pos) {

	if(pick.size() == m) {

		int ret = 0;
		for(const auto h: house) {
			int min_dis = INF;
			for(const auto p: pick){
				min_dis = min(min_dis, 
					abs(h.y - p.y) + abs(h.x - p.x));
			}
			ret += min_dis;
 		}

 		if (answer > ret)
 			answer = ret;

		return;
	}

	for(int i=pos; i<shop.size(); i++) {
		pick.push_back(shop[i]);
		DFS(i+1);
		pick.pop_back();
	}

}


int main() {

	scanf("%d %d", &n, &m);
	POSI target;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			scanf("%d", &type);
			target.y = i;
			target.x = j;

			if(type == 1) {
				house.push_back(target);
			}
			else if(type == 2) {
				shop.push_back(target);
			}
		}

	answer = INF;
	DFS(0);


	printf("%d\n", answer);
	return 0;
}

 

모든 치킨가게 목록에서 M 개를 뽑아 모든 부분집합을 구한 후, 각 경우의 도시의 치킨거리를 구한다.

최소의 값을 answer 에 저장하여 리턴한다.

 

처음 접근은 일반적인 방식으로 하나의 이차원 map 에 house, shop, blank를 모두 저장하려 했으나

각각의 경우를 나누어 계산을 해야 조합을 구하기가 시간복잡도가 낮았음.

 

시간초과가 계속해서 나서 size()를 많이 사용해서 그런것인지. abs() 가 느린함수여서 그런것인지 등의 원인을 생각하여

다양한 방법을 시도해보았으나, 결국 DFS(pos+1) -> DFS(i+1)로 호출하지 않아 발생한 이슈였다.

 

어떻게 테스트 케이스를 통과했는지 의문.. 아무튼 성공은 했다...ㅎㅎ