2주차(완전탐색) - [C++]백준15686 치킨 배달

13 Mar 2022 in Study on Algorithm

백준15686 치킨 배달 링크

문제

예제 입력

---

코드

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

int n, m, temp, value;
int result = 99999999;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	vector<bool> arr;

	cin >> n >> m;
	int num;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> num;
			if (num == 1)
				house.push_back({ i, j });
			else if (num == 2) {
				chicken.push_back({ i, j });
				arr.push_back(false);
			}
		}
	}

	for (int i = 0; i < m; i++)
		arr[i] = true;

	do {
		temp = 0;
		for (int i = 0; i < house.size(); i++) {
			int value = 99999999;
			for (int j = 0; j < chicken.size(); j++) {
				if (arr[j])
					value = min(value, abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second));
			}
			temp += value; // 모든 집당 최소값 = 도시 거리
		}
		result = min(result, temp);
	} while (prev_permutation(arr.begin(), arr.end()));

	cout << result;
}

설명

이 문제는 동네에 치킨집이 너무 많아 정해준 갯수의 치킨집만 남아야하는데 그중 모든 집과 최소거리를 구하여 출력합니다. 그 과정중에 조합(순열을 이용한)과 재귀함수 방식이 있는데 이번에 설명은 조합을 활용하여 구현했습니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<algorithm>
-prev_permutation(시작, 끝) : 배열에 있는 수를 이전순열로 만듬 더이상 이전 순열이 없다면 False
-next_permutation(시작, 끝) : 배열에 있는 수를 다음순열로 만듬 더이상 다음 순열이 없다면 False

---

결과