1. 문제 분석하기

1.1. 문제 의도

• 모든 경우의 수를 구한 뒤 최적해를 도출하는 bruteforce 문제입니다.

1.2. 문제 조건

1. 집의 개수는 최대 100개, 치킨집의 개수는 최대 13개다.

2. 문제 해결하기

• 모든 집을 기준으로 모든 치킨집에 대한 치킨거리 정보를 기록하는 2차원 테이블을 만듭니다.
• 치킨집 M개를 선택하는 조합 을 구합니다.
• 선택한 치킨집에 대해 각 집의 최소 치킨거리를 구합니다.
• 그들의 합을 구하고, 그 합들의 최소값이 정답입니다.

3. 코드

#include <iostream>
#include <algorithm>
#define MAX 2501	// 최대 지도크기 50x50 보다 큰 수
using namespace std;

int N, M, cntHouse, cntChicken, map[50][50], dist[100][13];
pair<int, int> house[100], chicken[13];

int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	// 사용자 예제 입력
	cin >> N >> M;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x) {
			cin >> map[y][x]; 
			if (map[y][x] == 1) house[cntHouse++] = {y, x};
			else if (map[y][x] == 2) chicken[cntChicken++] = {y, x};
		}
	// dist 배열 초기값 계산
	for (int i = 0; i < cntHouse; ++i)
		for (int j = 0; j < cntChicken; ++j)
			dist[i][j] = abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second);
	// 전체 치킨집 중 M개 선택
	bool comb[13] = {false, };
	for (int i = M; i < cntChicken; ++i) comb[i] = true;
	
	// 매 경우의 수에 대해 도시 치킨거리를 구하고 최소값 탐색.
	int answer = MAX;
	do {
		int sum = 0;
		for (int h = 0; h < cntHouse; ++h) {
			int d = MAX;
			for (int c = 0; c < cntChicken; ++c){
				if (comb[c]) continue;		// c번 치킨집은 선택되지 않았으므로 스킵.
				d = min(d, dist[h][c]);		// h번 집의 최소 치킨거리를 구함.
			}
			sum += d;						// 도시의 치킨거리 증가.
		}
		answer = min(answer, sum);			// 이번 경우의 수의 도시의 치킨거리가 더 작으면 갱신.
	} while(next_permutation(comb, comb + cntChicken));
	
	cout << answer;
}

4. 결과