[ 백준 ] 15686번 : 치킨 배달 - ( C++/C/CPP )

•  문제

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

15686번: 치킨 배달

---

• 풀이법 ( 알고리즘 )

처음엔 단순히 모든 치킨집과 집들의 거리를 계산해 그중 m개의 최소 수들을 구해 더했으나 tc부터 막혔다.

생각해보니 폐업을 시킨 후 도시의 치킨 거리를 구해야 하기 때문에 위의 방법은 틀린 방법이었다.

문제를 읽고 깊게 생각해보지 않으니 이런 황당한 실수를 하는 거 같다.

dfs를 돌며 모든 치킨집에 대해 계산했다면 폐업시키지 않은 치킨집과 각 집들의 거리 중 최소 거리를 구하고 더했다.

이후 최소 도시의 치킨 거리를 구해 출력해주었다.

1시간 동안 삽질했다.. 이런 실수는 줄이도록 노력해야겠다.

---

• 풀이 - C++

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 987654321

using namespace std;


int m, n, ans = MAX; // n : 도시의 넓이 n * n , m : 폐업하지 않는 치킨집의 개수 , ans : 답 저장
bool closing[14]; // closing[x] : x번째 치킨집을 폐업시켰는지 저장
vector <pair<int, int>> chicken, house;

void dfs(int idx, int cnt)
{
	if (idx > chicken.size()) return;

	if (cnt == m) //m개의 치킨집이 정해지면
	{
		int tmp = 0;
		for (int i = 0; i < house.size(); i++)
		{
			int d = MAX;

			for (int j = 0; j < chicken.size(); j++)
			{
				if (closing[j]) //j번째 치킨집을 사용한다면
				{
					d = min(d, abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second));
				}
			}
			tmp += d;
		}

		ans = min(ans, tmp);
		return;
	}

	closing[idx] = true; //현재 치킨집을 폐업하지 않는 경우
	dfs(idx + 1, cnt + 1);
	closing[idx] = false; //현재 치킨집을 폐업하는 경우
	dfs(idx + 1, cnt);
}

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

	//input
	cin >> n >> m;

	int t;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> t;
			if (t == 1)  house.push_back({ i,j }); //1은 집
			else if (t == 2) chicken.push_back({ i,j }); //2는 치킨집
		}
	}

	//solve
	dfs(0, 0);

	cout << ans;

	return 0;
}