BOJ : 15686 치킨 배달

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

 

---

[BOJ 15686 (G5) 리뷰]

 

처음에 문제 이해가 잘 안돼서 여러번 읽었다.

집과 치킨집과의 거리를 치킨거리라고 하는데 주어진 치킨집의 개수를 만족하며 존재하는 집의 치킨거리의 합이 최소가 되는경우를 구하면 된다. 모든경우를 탐색해야하므로 백트래킹을 이용했다.

 

전형적인 백트래킹이라 쓱쓱 구현해서 TC도 제대로 나오길래 제출했더니 시간초과가 떴다.

뭐가 문제인지 몰라서 Q&A를 확인해보니 치킨집의 경우에 대해 확인하는 과정에서 조합이 아닌 순열을 사용했기 때문이다. 예를들어 2번째 4번째 치킨집에 대해 확인을 했으면 4번째 2번째 치킨집의 경우는 확인을 안해도 되지만, 순열로 구현하면 모든 경우를 확인하게 된다. 그래서 시간초과가 나온것이였다.

 

조합으로 구현하기위해 재귀함수에 현재까지 확인한 index를 인자로 넘겼다.

그리고 제출했더니 정답처리 되었다.

---

 

#include <iostream>
#include <queue>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;

int board[51][51];
bool isUsed[15];
int N, M;
vector <pair<int, int>> chicken;

vector <pair<int, int>> house;

vector <pair<int, int>> current;
int ans = 987654321;
int cnt = 0; //치킨집 개수
int hcnt = 0; //집 개수
void go(int n,int val)
{
	if (n == M) //최대갯수 도달 최소거리 측정 후 최소 값 저장
	{
		int sum = 0;
		for (int i = 0; i < hcnt; i++)
		{
			auto cur = house[i];
			int temp = 987654321;
			for (int k = 0; k < M; k++)
			{
				int val = 0;
				auto rc = current[k];
				val = abs(cur.first - rc.first) + abs(cur.second - rc.second);
				temp = min(temp, val);
			}
			sum += temp;
		}

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

	for (int i = val; i < cnt; i++)
	{
		if (isUsed[i]) continue;
		isUsed[i] = 1;
		current.push_back(chicken[i]);
		go(n + 1,i);
		isUsed[i] = 0;
		current.pop_back(); 
	}


}


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

	cin >> N>>M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 2)
				chicken.push_back({ i,j });
			else if (board[i][j] == 1)
				house.push_back({ i,j });
		}
	}

	
	cnt = chicken.size();
	hcnt = house.size();
	go(0,0);
	cout << ans;

}