백준 15686번 치킨 배달

< 백준 15686번 치킨 배달 - 마포 코딩박>

사용한 알고리즘: DFS + 완전탐색


 치킨집을 (최대) M개만 남겼을때 도시의 치킨거리의 최솟값을 구하는 문제입니다.
저는 치킨집을 없애는 모든 경우를 DFS 를 돌려 답을 구했습니다.

문제풀이는 다음과 같습니다.
(1) (코드: 38~49)
 입력받을 때, 집의 위치, 치킨집 위치를 각각 pair 로 저장했습니다.
 없애야 되는 치킨집 수를 CNT 로 놓고 DFS를 돌립니다.

(2) (코드: 11~12)
 위치 A 와 B 사이의 거리를 문제에서 주어진 공식으로 구하는 함수를 만들었습니다.

(3) (코드: 14~34)
 과정 (1)에서 따로 모아둔 치킨집을 차례로 보면서,
 1. x번째 치킨집을 없애지 않고 x+1번째로 재귀
 2. x번째 치킨집을 없애고 (set에 저장) x+1번째로 재귀
 과정을 통해 DFS 를 돌렸습니다.
 없앤 치킨집이 CNT 인 경우 도시의 치킨거리를 계산해주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 50;
	typedef pair<int, int> pii;
	int N, M, H, S, CNT;
	int ans = 11111;
	vector<pii> house;
	vector<pii> store;
	// a, b 집 간의 거리
	int PATH(int a, int b){
	return abs(house[a].first-store[b].first)+abs(house[a].second-store[b].second);
	}
	void DFS(int idx, set<int> no){
	// 없앤 치킨집이 CNT개이면 답을 도출
	if(no.size()==CNT){
	int Total = 0;
	// 도시의 치킨거리 계산
	for (int i = 0; i < H; ++i){
	int dis = 11111;
	for (int j = 0; j < S; ++j){
	if(no.count(j)) continue;
	dis = min(dis,PATH(i,j));
	}
	Total+=dis;
	}
	ans = min(Total,ans);
	}
	if(idx>=S) return;
	// idx번째 치킨집 안없앰
	DFS(idx+1,no);
	// idx번째 치킨집 없앰
	no.insert(idx);
	DFS(idx+1,no);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	int num;
	cin >> num;
	if(num==1) house.push_back(pii(i,j));
	else if(num==2) store.push_back(pii(i,j));
	}
	}
	H = house.size();
	S = store.size();
	// 없애야 되는 치킨집 수
	CNT = S-M;
	set<int> NO;
	DFS(0,NO);
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 15686.cpp hosted with ❤ by GitHub