[백준] 15686 치킨 배달

[백준] 15686 치킨 배달

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

• 치킨집 M개 선택 비트마스크로 표현할 때, 비스마스크 범위에 주의하자
  bitmask <= ((1 << chickens.size()) - 1)

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
#include <algorithm>
using namespace std;

//bitmask에 포함된 원소의 개수 반환
int bitmaskCnt(int bitmask) {
	int cnt = 0;
	while (bitmask > 0) {
		cnt += (bitmask % 2);
		bitmask /= 2;
	}
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	//도시
	vector<vector<int>> board(N, vector<int>(N));

	//도시의 집 좌표들
	vector<pair<int, int>> houses;
	//도시의 치킨집 좌표들
	vector<pair<int, int>> chickens;
	
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int input;
			cin >> input;
			board[i][j] = input;

			//좌표 1부터 시작하도록 1 더해줌
			if (input == 1)
				houses.push_back({ i + 1, j + 1 });
			else if (input == 2)
				chickens.push_back({ i + 1, j + 1 });
		}
	}

	//치킨 거리의 합의 최솟값
	int minSum = 987654321;

	//치킨집 M개 선택 비트마스크로 표현
	for (int bitmask = 0; bitmask <= ((1 << chickens.size()) - 1); ++bitmask) {
		if (bitmaskCnt(bitmask) != M) continue;

		//비트마스크대로 M개의 치킨집을 선택했을 때
		//치킨 거리의 합
		int sum = 0;
		for (int i = 0; i < houses.size(); ++i) {
			//houses[i] 집의 치킨 거리
			int minDist = 987654321;

			for (int j = 0; j < chickens.size(); ++j) {
				//chickens[j] 치킨집 비트마스크에 포함된 경우
				if (bitmask & (1 << j)) {
					int dist = abs(houses[i].first - chickens[j].first) + abs(houses[i].second - chickens[j].second);
					minDist = min(minDist, dist);
				}
			}
			sum += minDist;
		}
		minSum = min(minSum, sum);
	}

	cout << minSum;
	return 0;
}