[DFS] BJ15686 치킨 배달

문제 출처: https://www.acmicpc.net/problem/15686

 

Solution

• DFS로 닫을 가게를 고르고, 그 때의 치킨 거리를 구해서 최소 값을 갱신해나간다.

Point

• 문제의 조건에는 닫지 않을 가게의 수 M이 주어지지만, 가게 정보가 2로 주어지므로, 닫지 않을 가게(c.size()-M)를 고르는 것이 더 편하다.
• DFS 탐색에서 경우의 수를 고를 때, for 문의 i를 cc부터 하는 것이 효율적이다.
• 거리 계산할 때, 복잡하게 BFS 같은 탐색 생각하지 말고 직관적으로 바로 구하는 것이 더 낫다.

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M;
int map[50][50];
vector<pair<int, int>> c;
vector<pair<int, int>> h;
int result;

void input() {
	result = 987654321;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) h.push_back({ i, j });
			if (map[i][j] == 2) c.push_back({ i, j });
		}
	}
}

int dist() {
	int d = 0;
	for (int i = 0; i < h.size(); i++) {
		int hd = 987654321;
		for (int j = 0; j < c.size(); j++) {
			if(map[c[j].first][c[j].second] == 2)
				hd = min(hd, abs(h[i].first - c[j].first) + abs(h[i].second - c[j].second));
		}
		d += hd;
	}
	return d;
}

void chooseDFS(int d, int cc) {
	if (d == (c.size() - M)) { //# of closing stores
		result = min(result, dist());
		return;
	}
	for (int i = cc; i < c.size(); i++) {
		map[c[i].first][c[i].second] = 0; //close
		chooseDFS(d + 1, i + 1);
		map[c[i].first][c[i].second] = 2;
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	input();
	chooseDFS(0, 0);
	dist();
	cout << result << endl;
}