백준 15686번 치킨 배달

 

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

15686번: 치킨 배달

 

문제를 읽었을 때 전반적으로 어렵거나 이해가지 않는 내용은 딱히 없었다.

전체 치킨집에서 M개만큼 선택할 수 있는 모든 경우의 수를 구하고 각 경우의 수마다 도시의 치킨 거리를 구하면 된다.

여기서 전체 치킨집 중에서 최대 M개만큼 고를 수 있다고 했으므로 M개보다 적게 뽑아도 되지만 실제로는 반드시 M개를 꽉 채워서 뽑아야 한다. 선택할 수 있는 최대치인 M개만큼 뽑아야 항상 최소값을 보장하기 때문이다.

 

집, 치킨집의 좌표를 저장할 공간으로 vector<pair<int, int>>를 이용하였다.

 

접근 순서는 다음과 같다.

- 입력으로 받는 집과 치킨집의 좌표를 각각 서로 다른 vector에 저장한다.

 

1. 전체 치킨집 중에서 치킨집을 하나씩 선택하여 M개까지 뽑는다.

2. M개의 치킨집을 뽑았으면, 도시에 있는 집과 치킨집의 치킨거리를 계산한 뒤 도시의 치킨거리를 구한다.

3. 위 과정을 뽑을 수 있는 모든 경우의 수만큼 반복한다.

 

 

선택된 치킨집의 좌표는 새로운 vector에 저장하면서 M개를 뽑을 수 있는 모든 경우의 수를 구하기 위해 재귀함수를 이용하였다.

 

for (int i = num; i < chicken.size(); i++) {
		//치킨집 선택후 벡터에 삽입
		selected_chicken.push_back(chicken[i]);
		dfs(cnt + 1, i + 1);
		selected_chicken.pop_back();
}

 

0~4까지 5개의 치킨집이 있고 M이 3일 때

0 1 2

0 1 3

0 1 4

0 2 3

0 2 4

0 3 4

1 2 3

1 2 4

1 3 4

2 3 4까지 총 10개의 경우의 수가 나온다.

0 1 2를 뽑는 경우랑 0 2 1를 뽑는 경우가 같기 때문에 저런 케이스를 굳이 한 번 더 계산할 필요는 없다.

 

 

 

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <utility>
#include <deque>
#include <math.h>
using namespace std;

vector<pair<int, int>> home;
vector<pair<int, int>> chicken;
vector<pair<int, int>> selected_chicken;



int n, m;
int ans = 999999;
int cnt_home = 0;
int tot_distance = 0;
int cnt = 0;
int map[51][51] = { 0 };
int chicken_distance[101] = { 0 };

void dfs(int cnt, int num) {

	//치킨집 m개 뽑았을 때
	if (cnt == m) {

		//거리 계산하기
		for (int i = 0; i < cnt_home; i++) {
			int hx = home[i].first;
			int hy = home[i].second;

			for (int j = 0; j < m; j++) {
				int cx = selected_chicken[j].first;
				int cy = selected_chicken[j].second;

				chicken_distance[i] = min(chicken_distance[i], (abs(hx - cx) + abs(hy - cy)));
			}
		}

		//도시의 치킨거리 계산
		for (int i = 0; i < cnt_home; i++) {
			tot_distance += chicken_distance[i];
		}

		ans = min(ans, tot_distance);

		
		//초기화
		tot_distance = 0;
		

		for (int i = 0; i < cnt_home; i++)
			chicken_distance[i] = 999999;

		return;
	}




	for (int i = num; i < chicken.size(); i++) {
		//치킨집 선택후 벡터에 삽입
		selected_chicken.push_back(chicken[i]);
		dfs(cnt + 1, i + 1);
		selected_chicken.pop_back();
	}

}


int main() {

	cin >> n >> m;


	//map 입력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];

			//집의 좌표는 벡터에 저장
			if (map[i][j] == 1) {
				home.push_back(make_pair(i, j));
				cnt_home++;
			}

			//치킨가게 위치 벡터에 저장
			if (map[i][j] == 2) {
				chicken.push_back(make_pair(i, j));
			}
		}
	}

	for (int i = 0; i < cnt_home; i++)
		chicken_distance[i] = 999999;


	dfs(0, 0);
	cout << ans << endl;




	return 0;

}

 

 

 

브루트포스 문제를 풀면서 가장 어려워하는 부분은 모든 경우를 탐색하기 위한 코드를 적절히 구현하는 것이다.

머릿속으로는 브루트포스 문제인걸 알겠는데 이걸 어떻게 구현하는지가 쉽지가 않다. 문제를 많이 풀면서 적당한 시간만큼 고민해보고 다른 사람이 풀었던 코드를 참고하면서 좋은 아이디어를 활용하고 구현능력을 기르는 것이 중요한 것 같다.