[백준] 15686번 치킨 배달 C++ 문제풀이

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

15686번: 치킨 배달

문제 풀이

완전탐색 문제였다. 

맨 처음에는 재귀부분에 visited 배열을 만들어서 방문을 안 한 경우에 대해서 재귀를 수행했는데 시간초과가 나왔다.

for (int i = 0; i < chicken.size(); i++) {
	if (visited[i] == false) {				
		visited[i] = true;
		ch_chck.push_back(chicken[i]);
		dfs(cnt+1);
		ch_chck.pop_back();
		visited[i] = false;
	}
}

for문을 0부터 치킨집 배열 전체에 대해 반복해서 시간초과가 나온 것 같다.

따라서 for문 반복의 시작을 바로 이전의 선택한 치킨집 이후부터 탐색하게 코드를 작성했다.

결과적으로 문제를 해결할 수 있었다.

 

소스 코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;
vector<pair<int, int>> ch_chck; //선택한 치킨집.
int vilage[51][51] = { 0 };
int result = 1e+10;

void dfs(int cnt, int idx) {
	if (cnt == M) {
		int total_min_distance = 0;
		for (int i = 0; i < home.size(); i++) {
			int min_distance = 1000;
			int dx = home[i].first;
			int dy = home[i].second;
			for (int j = 0; j < ch_chck.size(); j++) {
				int cx = ch_chck[j].first;
				int cy = ch_chck[j].second;
				int distance = abs(cx - dx) + abs(cy - dy);
				min_distance = min(min_distance, distance);
			}
			total_min_distance += min_distance;
		}
		result = min(result, total_min_distance);
	}
	else {
		for (int i = idx; i < chicken.size(); i++) {
			ch_chck.push_back(chicken[i]);
			dfs(cnt + 1, i + 1);
			ch_chck.pop_back();
		}
	}
}

int main() {
	//시간초과때문에 넣음.
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int a;
			cin >> a;
			if (a == 1) {
				home.push_back(make_pair(i, j));
				vilage[i][j] = 1;
			}
			else if (a == 2) {
				chicken.push_back(make_pair(i, j));
				vilage[i][j] = 2;
			}
		}
	}
	dfs(0, 0);
	cout << result << '\n';
}