[C++] BOJ(백준) 15686 치킨 배달

 

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

15686번: 치킨 배달

 

브루트포스와 백트래킹 문제다.

 

1. m개의 치킨 집 선택

2. 각 집에서 치킨 집의 가장 가까운 거리를 구하고 모든 집에서의 거리 합 구하기

3. 모든 조합의 경우에서 2번을 수행해 최소 거리 구하기

로 방법을 생각했다.

 

m개의 치킨 집을 선택하기 위해서는 재귀 백트래킹을 사용했다.

집과 치킨 집의 거리를 구하기 위해서는 좌표 계산을 했다.

DFS와 백트래킹 공부 중인 나머지 거리를 구할 때도 백트래킹을 사용하려 했다...

이 부분에서 시간을 한참 썼다.

 

그리고 C++에는 조합 방법으로 함수가 존재한다는 것을 알았다.

algorithm 헤더파일에 포함된 next_permutation함수인데 이 부분은 공부를 더 해봐야 할 것 같다.

 

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

int n, m, chick, home;
int res = INT_MAX;
int arr[13];
bool visit[13];
pair<int, int> chicken[13];
pair<int, int> house[100];

void distance() {
	// 각 집을 기준으로 가장 가까운 치킨 집 탐색
	int sum = 0;
	for (int i = 0; i < home; i++) {
		int dist = 100;
		for (int j = 0; j < m; j++) {
			// 집에서 치킨 집 까지의 거리
			int garo = abs(house[i].first - chicken[arr[j]].first);
			int sero = abs(house[i].second - chicken[arr[j]].second);
			// 거리 중 최솟값
			dist = min(dist, garo + sero);
		}
		// 모든 집에서의 치킨 집 거리 합
		sum += dist;
	}
	// 거리 합 중 최솟값
	res = min(res, sum);
}

void searchM(int num, int cnt) {
	// m개가 선택됐다면 거리 계산 후 종료
	if (cnt == m) {
		// 거리 계산 함수
		distance();
		return;
	}

	/*
	순서만 다른 조합은 같은 것으로 구분하기 때문에
	항상 이전 수보다 큰 수를 탐색
	*/
	for (int i = num; i < chick; i++) {
		if (!visit[i]) {
			visit[i] = true;
			arr[cnt] = i;
			searchM(i + 1, cnt + 1);
			visit[i] = false;
		}
	}
}

int main() {
	// 입출력 속도 향상을 위함
	ios::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) house[home++] = { i, j };
			else if (a == 2) chicken[chick++] = { i, j };
		}
	}

	// m개의 치킨집 고르기
	searchM(0, 0);
	cout << res;
}

오류, 실패 없이 한 번에 성공해서 짜릿하다 (≧∇≦)ﾉ