[BOJ] 15686: 치킨 배달

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

15686번: 치킨 배달

간단한 문제다.

 

순열을 생성해서 풀 수도 있고, 재귀함수로 가능한 경우를 모두 탐색해도 풀 수 있고, 비트마스킹을 써서 풀 수도 있다.

 

재귀함수로 가능한 경우를 모두 탐색하는 경우는

치킨 집이 N개 존재한다면, N개의 치킨집에 대해 각각 고른다/고르지 않는다를 선택할 수 있으니 O(2^N)이다.

 

순열이나 비트마스킹으로 푸는 경우 또한 치킨집의 개수가 N개일 때, (1<<N)번 반복하기 때문에 O(2^N)이다.

치킨집은 최대 13개이니, 2^13 = 8192로 넉넉하게 풀 수 있다.

 

int minDist = 10e8;
for (int i = 1; i < (1 << numOfChickens); ++i) {
  int cnt = __builtin_popcount(i);
  if (cnt > M) continue;
  minDist = std::min(minDist, getAllDistances(i));
}

 

비트마스킹으로 풀 경우 달라지는 부분이다.

 

int solve(int index, int count = 0) {
	if (index == numOfChickens) {
		return (count <= M) ? getAllDistances() : 10e8;
	}

	int ret = solve(index + 1, count);

	if (count < M) {
		std::get<2>(chickens[index]) = true;
		ret = std::min(ret, solve(index + 1, count + 1));
		std::get<2>(chickens[index]) = false;
	}
	return ret;
}

 

재귀함수로 풀 경우 달라지는 부분이다.

 

 

 

비트마스킹 전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int N, M;
int a[50][50];
std::vector<std::pair<int, int>> chickens;
std::vector<std::pair<int, int>> houses;
int numOfChickens;

int getDistance(int r1, int c1, int r2, int c2) {
	return abs(r1 - r2) + abs(c1 - c2);
}

int getAllDistances(int state) {
	int distance = 0;
	for (const auto& house : houses) {
		int minDistance = 0;
		for (int i = 0; i < numOfChickens; ++i) {
			if ((state & (1 << i)) == 0) continue;
			int r2 = chickens[i].first, c2 = chickens[i].second;
			int dist = getDistance(house.first, house.second, r2, c2);
			if (minDistance == 0)
				minDistance = dist;
			else
				minDistance = std::min(minDistance, dist);
		}
		distance += minDistance;
	}
	if (distance == 0) {
		distance = 10e8;
	}
	return distance;
}

int main() {
  std::cin >> N >> M;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      std::cin >> a[i][j];
      if (a[i][j] == 1) {
        houses.push_back({ i, j });
      }
      if (a[i][j] == 2) {
        chickens.push_back({ i, j });
      }
    }
  }

  numOfChickens = chickens.size();

  int minDist = 10e8;
  for (int i = 1; i < (1 << numOfChickens); ++i) {
    int cnt = __builtin_popcount(i);
    if (cnt > M) continue;
    minDist = std::min(minDist, getAllDistances(i));
  }

  std::cout << minDist;

  return 0;
}

 

재귀함수 전체 코드

#include <iostream>
#include <vector>
#include <tuple>
#include <cmath>
#include <algorithm>

int N, M;
int a[50][50];
std::vector<std::tuple<int, int, bool>> chickens;
std::vector<std::pair<int, int>> houses;
int numOfChickens;

int getDistance(int r1, int c1, int r2, int c2) {
	return abs(r1 - r2) + abs(c1 - c2);
}

int getAllDistances() {
	int distance = 0;
	for (const auto& house : houses) {
		int minDistance = 0;
		for (const auto& chicken : chickens) {
			int r2, c2; bool active;
			std::tie(r2, c2, active) = chicken;
			if (!active) continue;

			int dist = getDistance(house.first, house.second, r2, c2);
			if (minDistance == 0)
				minDistance = dist;
			else
				minDistance = std::min(minDistance, dist);
		}
		distance += minDistance;
	}
	if (distance == 0) {
		distance = 10e8;
	}
	return distance;
}

int solve(int index, int count = 0) {
	if (index == numOfChickens) {
		return (count <= M) ? getAllDistances() : 10e8;
	}

	int ret = solve(index + 1, count);

	if (count < M) {
		std::get<2>(chickens[index]) = true;
		ret = std::min(ret, solve(index + 1, count + 1));
		std::get<2>(chickens[index]) = false;
	}
	return ret;
}

int main() {
	std::cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			std::cin >> a[i][j];
			if (a[i][j] == 1) {
				houses.push_back({ i, j });
			}
			if (a[i][j] == 2) {
				chickens.push_back({ i, j, false });
			}
		}
	}
	numOfChickens = chickens.size();
	std::cout << solve(0);

	return 0;
}