[C++] 백준 15686번: 치킨 배달

문제 링크

15686번: 치킨 배달

문제 요약

도시에 치킨집과 집이 있다. 도시의 모든 집에서 가장 가까운 치킨집까지의 거리의 합을 치킨 거리라고 한다. 치킨집을 M개만 남기고 나머지는 문을 닫으려고 할 때, 치킨 거리를 최소화시켜야 한다.

접근 방법

간단한 문제였지만 실수로 인해서 TLE를 받았었습니다.

치킨 집의 수가 최대 13이고, 집의 수는 최대 2N입니다. 13에서 임의의 M개를 뽑아야 합니다.

그런데 $1\leq x \leq 13$인 $x$에 대해서 $_{13}C_{x}$값들이 그렇게 크게 나오지 않습니다. $_{13}C_{6}$이 1716 정도로 가장 큽니다. 또한 N은 최대 50이기 때문에 치킨집과 집 사이의 거리를 전부 비교하는 횟수도 그렇게 크지 않습니다. 따라서 모든 치킨집 조합을 고려하는 브루트포스 알고리즘을 이용해 풀 수 있습니다.

먼저 집과 치킨집의 위치를 모두 기록하고, 모든 가능한 쌍의 거리를 미리 구해 둡니다. 그리고 M개의 치킨집을 골라가면서 최솟값을 갱신하면 됩니다.

정말 간단한 문제였는데, 백트래킹 코드를 작성할 때

void func(int cnt)
{
	if (cnt == m)
	{
    		//something
		return;
	}

	for (int i = 0; i < chicken.size(); i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			func(cnt + 1);
			visited[i] = false;
		}
	}
}

이런식으로 작성해서 TLE를 받았습니다. for문 내에서 i가

void func(int cnt, int idx)
{
	if (cnt == m)
	{
		//something
		return;
	}

	for (int i = idx; i < chicken.size(); i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			func(cnt + 1, i + 1);
			visited[i] = false;
		}
	}
}

이런식으로, 재귀호출하기 전의 바로 다음 인덱스부터 시작해야 했는데, 안일하게 풀다가 저런식으로 제출을 해버렸습니다. 제가 만든 TC가 제 PC에서는 빠르게 돌아가서 문제가 있다는 사실조차 인지하지 못하였습니다.

방심하지 말고 매번 페널티를 주의하면서 풀어야겠다는 생각이 들었습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, m, res = INT_MAX, dist[105][15];
vector<pair<int, int>> house, chicken;
bool visited[13];

void func(int cnt, int idx)
{
	if (cnt == m)
	{
		int len = 0;
		for (int i = 0; i < house.size(); i++)
		{
			int val = INT_MAX;
			for (int j = 0; j < chicken.size(); j++)
				if (visited[j])
					val = min(val, dist[i][j]);
			len += val;
		}
		res = min(res, len);
		return;
	}

	for (int i = idx; i < chicken.size(); i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			func(cnt + 1, i + 1);
			visited[i] = false;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int num;
			cin >> num;

			if (num == 1)
				house.push_back({ i, j });
			else if (num == 2)
				chicken.push_back({ i, j });
		}
	}

	for (int i = 0; i < house.size(); i++)
		for (int j = 0; j < chicken.size(); j++)
			dist[i][j] = abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second);

	func(0, 0);
	cout << res;
	return 0;
}