백준 15686 - 치킨 배달

문제링크

• 백준 15686

문제설명

• N x N 크기의 도시가 주어진다. 도시는 1x1 크기의 칸으로 나누어져 있고, 도시의 각 칸은 빈 칸(0), 집(1), 치킨집(2) 중 하나이다.
• 치킨 거리 는 집과 가장 가까운 치킨집 사이의 거리이다. 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다.
• 도시의 치킨 거리 는 모든 집의 치킨 거리의 합이다.
• 거리는 맨하탄 거리 공삭을 따른다.
  • dist = abs(x1-x2) + abs(y1-y2)
• 주어진 치킨집 중 M개만 뽑았을 때 도시의 치킨 거리의 최솟값을 구하라

문제접근

• 배열 vector<pair<int, int>> chickenStore 을 선언하여 치킨집의 좌표를 담는다.
• 치킨집 중 M개를 뽑는 로직은 재귀호출로 구현할 수 있다.
• 각각의 집에서 가장 가까운 치킨집까지의 치킨 거리를 구하는 로직은 두가지 정도 아이디어가 있었다.
  • 각각의 집에 대하여 너비우선탐색으로 치킨집을 방문하게 되면 해당 치킨 거리를 반환한다. -> 시간초과
  • 집과 치킨집의 좌표를 명확하게 알고 있으므로 맨하탄 거리 공식으로 수식을 적용해서 구한다. -> 빠르고 간결함

구현

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

int N, M;
int visited[13];
vector<pair<int, int>> chickenStore;
vector<pair<int, int>> house;
vector<pair<int, int>> cand;

int getDist(pair<int, int> hpos) {
	int dist =10000;
	for (auto chicken : cand) {
		dist = min(dist, abs(chicken.first - hpos.first) + abs(chicken.second - hpos.second));
	}
	return dist;
}

int getChickenDist(int v, int cnt) {
	if (cnt == M) {
		int dist = 0;
		for (auto ele : house) {
			dist += getDist(ele);
		}
		return dist;
	}

	int ret = 10000;
	for (int i = v; i < chickenStore.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		cand.push_back(chickenStore[i]);
		ret = min(ret, getChickenDist(i + 1, cnt + 1));
		cand.pop_back();
		visited[i] = false;
	}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	scanf("%d %d", &N, &M);
	int val = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &val);
			if (val == 1) house.push_back(make_pair(r, c));
			else if (val == 2) chickenStore.push_back(make_pair(r, c));
		}
	}

	int ans = getChickenDist(0, 0);
	printf("%d", ans);
	return 0;

}