[백준][15686] 치킨 배달

이 포스트는 백준 사이트의 치킨 배달 문제 풀이입니다.

문제

첫 번째 시도(실패)

여러 개의 치킨 가게 중 M 개만 선택하였을 때, 도시의 치킨 거리가 최소인 경우를 구해야 합니다.
여기서 M 개의 가게 선택을 위해 조합을 사용하고
조합으로 선택된 가게들에서 집들까지의 최소 거리를 반복해서 갱신해 정답을 구하고자 하였습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define IO_SETTING std::ios::sync_with_stdio(false)
#define INPUT_SETTING std::cin.tie(0)

int N, M;
vector<vector<int>> board;
vector<vector<int>> store;
vector<vector<int>> store_combination;
vector<vector<int>> distance_log;

void input() {
	cin >> N >> M;
	board.assign(N, vector<int>(N, 0));

	for (int row = 0; row < N; ++row) {
		for (int col = 0; col < N; ++col) {
			cin >> board[row][col];

			if (board[row][col] == 2) {
				store.emplace_back(vector<int>{row, col});
			}
		}
	}
}

void make_store_combination() {
	vector<bool> select(N, false);
	for (int number = 0; number < M; ++number) {
		select[number] = true;
	}

	do {
		vector<int> curr_store_combination;
		for (int number = 0; number < N; ++number) {
			if (select[number]) {
				curr_store_combination.push_back(number);
			}
		}
		store_combination.push_back(curr_store_combination);
	} while (prev_permutation(select.begin(), select.end()));
}

void refresh_chicken_distance(int start_row, int start_col) {
	// clockwise direction (00 ~ 12)
	int dir_row[8]{ -1, -1, 0, 1, 1, 1, 0, -1 };
	int dir_col[8]{ 0, 1, 1, 1, 0, -1, -1, -1 };

	queue<vector<int>> q;
	q.push({ start_row, start_col, 0 });
	vector<vector<bool>> visited(N, vector <bool>(N, false));
	visited[start_row][start_col] = true;

	while (false == q.empty()) {
		vector<int> point = q.front();
		q.pop();

		for (int dir = 0; dir < 8; ++dir)
		{
			int new_row = point[0] + dir_row[dir];
			int new_col = point[1] + dir_col[dir];

			if (new_row < 0 || new_row >= N || new_col < 0 || new_col >= N)
				continue;
			if (visited[new_row][new_col])
				continue;

			visited[new_row][new_col] = true;
			int curr_distance = (abs(new_row - start_row) + abs(new_col - start_col));

			if (1 == board[new_row][new_col]) {
				distance_log[new_row][new_col] 
					= min(curr_distance, distance_log[new_row][new_col]);
			}
			else {
				q.push({ new_row, new_col, point[2] + 1 });
			}
		}
	}
}

int get_city_chicken_distance() {
	
	int min_distance = 2e9;

	for (auto points : store_combination) {
		distance_log.assign(N, vector<int>(N, 2e9));
		for (int store_number : points) {
			refresh_chicken_distance(store[store_number][0], store[store_number][1]);
		}

		int curr_distance = 0;
		for (int row = 0; row < N; ++row) {
			for (int col = 0; col < N; ++col) {
				if (board[row][col] == 1) {
					curr_distance += distance_log[row][col];
				}
			}
		}
		min_distance = min(min_distance, curr_distance);

		if (store.size() == M) {
			break;
		}
	}
	return min_distance;
}

int main() {
	input();
	make_store_combination();
	cout << get_city_chicken_distance();
	return 0;
}

그러나 위의 코드는 메모리 초과로 인해서 오답이 되었습니다.
그래서 사용하지 않는 데이터를 없애기 위해
지도 전체를 저장하는 board 를 제거하고
대신 모든 집과 치킨 가게의 위치만 저장 하는 houses, store 벡터를 만들었습니다.

그리고 이전처럼 치킨 가게들의 조합을 구한 뒤
선택된 가게에서 각 집까지의 거리를 구해 최소의 도시의 치킨 거리를 구했습니다.

두 번째 시도(정답)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define IO_SETTING std::ios::sync_with_stdio(false)
#define INPUT_SETTING std::cin.tie(0)

int N, M;
vector<vector<int>> houses;
vector<vector<int>> store;
vector<vector<int>> store_combination;

void input() {
	cin >> N >> M;
	for (int row = 0; row < N; ++row) {
		for (int col = 0, temp; col < N; ++col) {
			cin >> temp;
			if (temp == 1) {
				houses.emplace_back(vector<int>{row, col});
			} else if (temp == 2) {
				store.emplace_back(vector<int>{row, col});
			}
		}
	}
}

void make_store_combination() {
	vector<bool> select((int)store.size(), false);
	for (int number = 0; number < M; ++number) {
		select[number] = true;
	}

	do {
		vector<int> curr_store_combination;
		for (int number = 0; number < (int)store.size(); ++number) {
			if (select[number]) {
				curr_store_combination.push_back(number);
			}
		}
		store_combination.push_back(curr_store_combination);
	} while (prev_permutation(select.begin(), select.end()));
}

int get_city_chicken_distance() {
	int city_chicken_distance = 2e9;
	for (auto alive_store : store_combination) {

		int alive_store_distance = 0;
		for (auto house_position : houses) {
			int curr_distance = 2e9;
			for (int number : alive_store) {
				int distance = abs(house_position[0] - store[number][0]) + abs(house_position[1] - store[number][1]);
				curr_distance = min(curr_distance, distance);
			}
			alive_store_distance += curr_distance;
		}
		city_chicken_distance = min(city_chicken_distance, alive_store_distance);
	}
	return city_chicken_distance;
}

int main() {
	input();
	make_store_combination();
	cout << get_city_chicken_distance();
	return 0;
}