[백준] 15686-치킨 배달(C++)

문제링크:www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

간단한 dfs 문제였습니다. 

백트래킹의 요소는 잘 모르겠습니다. 단지 가까운 치킨 가게를 찾을때 bfs 탐색의 개념을 사용하지 말고, 각각의 치킨집과 집의 거리를  |r1-r2| + |c1-c2| 공식을 통해서 찾아주게끔만 구현해주면 맞는 간단한 문제입니다.

 

저는 치킨집 좌표를 구조체 벡터를 사용해서, 집 좌표는 pair사용해서 구현했습니다. 

 

 

아래는 정답 코드입니다. 

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

typedef struct a{
	int y;
	int x;
	bool checked;
}Chk;

vector <pair <int, int>> house;
vector <Chk> chicken;
int n = 0, m = 0;
int result = 2e9;

void dfs(int cnt, int current) {

	if (cnt == m) {
		/*
		for (int i = 0; i < chicken.size(); i++) {
			if (chicken[i].checked == true)
				cout << i << ' ';
		}
		cout << endl;*/

		int sum = 0;

		for (int i = 0; i < house.size(); i++) {
			int mined = 1000000000;
			for (int j = 0; j < chicken.size(); j++) {
				if (chicken[j].checked == false) continue;

				mined = min(mined, abs(house[i].first - chicken[j].y) + abs(house[i].second - chicken[j].x));
			}
			sum += mined;
		}

		if (result > sum)
			result = sum;

		return;
	}
	

	for (int i = current; i < chicken.size(); i++) {
		if (chicken[i].checked == false) {
			chicken[i].checked = true;
			dfs(cnt + 1, i);
			chicken[i].checked = false;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	// 1.
	cin >> n >> m;
	int num = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			cin >> num;
			if (num == 1)
				house.push_back(make_pair(i, j));
			else if (num == 2)
				chicken.push_back({ i,j,0 });
		}
	//2.
	dfs(0, 0);

	cout << result << endl;
	return 0;
}