백준 치킨배달(복습)

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

15686번: 치킨 배달

다시한번 문제를 풀어봤습니다. 다시 풀었는데도 한번에 못푸는거 보면  이 알고리즘에 대해서 부족하다는걸 다시 한번 느끼네요. 

struct Data {
	int i;
	int j;
};

struct gData {
	vector<int>save;
};


int n, m;
vector<vector<int>>maps;
vector<Data>chickHouse;
vector<Data>House;
vector<bool>bVisited;
vector<int>save;
vector<vector<int>>gsave;
vector<int>mins;
void backtracking(int k,int cnt) {
	if (m == cnt) {
		gsave.push_back(save);
	
	}
	//cout << k << ",";
	for (int i = k; i < chickHouse.size(); i++) {
		if (bVisited[i] == false) {
			bVisited[i] = true;
			save.push_back(i);
			backtracking(i, cnt + 1);
			save.pop_back();
			bVisited[i] = false;
		}
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//nxn
	//도시 1x1
	//rc 
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		vector<int>tmpMaps;
		for (int j = 0; j < n; j++) {
			int tmp;
			cin >> tmp;
			if (tmp == 2) {
				Data d;
				d.i = i;
				d.j = j;
				chickHouse.push_back(d);
				bVisited.push_back(false);
			}
			if ( tmp == 1 ) {
				Data d;
				d.i = i;
				d.j = j;
				House.push_back(d);
				mins.push_back(-1);
			}
			tmpMaps.push_back(tmp);
		}
		maps.push_back(tmpMaps);
	}
	//r1-r2+c1+c2
	//0빈칸 1은 집 2는 치킨집
	//치킨집 최대갯수 m개 
	//도시의 치킨 거리
	backtracking(0, 0);
	
	//거리값계산
   int gsum = -1;
	for (int i = 0; i < gsave.size(); i++) {
		int sums = 0;
		for (int t = 0; t < House.size(); t++) {
			int mins = -1;
			for (int j = 0; j < gsave[i].size(); j++) {
				int r = chickHouse[gsave[i][j]].i+1;
				int c = chickHouse[gsave[i][j]].j+1;
				int tmpmin = abs(House[t].i+1 - r) + abs(House[t].j+1 - c);
					
				if (mins == -1) {
					mins = tmpmin;
				}
				else {
					mins = min(mins, tmpmin);
				}
			}
			sums += mins;
			}
			if (gsum == -1) {
				gsum = sums;
			}
			else {
				gsum = min(sums, gsum);
			}
			
		}
		cout << gsum ;
	return 0;
}