[백준/C++] 15686번: 치킨 배달

문제

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

---

문제 요약

1 × 1 크기의 칸으로 이루어진 N × N 크기의 도시가 있다.

 

각 칸은 빈 칸, 치킨집, 집 중 하나이다.

 

집과 가장 가까운 치킨집 사이의 거리를 "집의 치킨 거리"라고 한다.

 

모든 집의 치킨거리를 "도시의 치킨 거리"라고 한다.

 

도시 내 치킨집 중 최대 M개를 고르고 나머지 치킨집은 폐업시켜야할 때,

도시의 치킨 거리가 가장 작게 만들어야 한다.

 

도시의 치킨 거리의 최솟값을 출력한다.

---

코드

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

using namespace std;

int n, m;

int board[55][55];

vector<pair<int, int>> home;
vector<pair<int, int>> chicken;

bool open_chicken[20];

int res = 1e9;

void dfs(int idx, int cnt) {
	// 치킨집 m개가 골라졌을 경우
	if (cnt == m) {
		// 도시의 치킨 거리
		int city_dist = 0;

		// 각 집의 치킨거리 계산
		for (auto& h : home) {
			int hx = h.first;
			int hy = h.second;

			int home_dist = 1e9;

			for (int i = 0; i < chicken.size(); i++) {
				if (open_chicken[i]) {
					int cx = chicken[i].first;
					int cy = chicken[i].second;
					int dist = abs(hx - cx) + abs(hy - cy);
					if (dist < home_dist) {
						home_dist = dist;
					}
				}
			}
			city_dist += home_dist;
		}
		res = min(res, city_dist);
		return;
	}

	if (idx >= chicken.size()) return;

	open_chicken[idx] = true;
	dfs(idx + 1, cnt + 1);

	open_chicken[idx] = false;
	dfs(idx + 1, cnt);
}

int main() {
	// 입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	// 도시 정보 입력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];

			if (board[i][j] == 1) {
				home.push_back({ i, j });
			}
			else if (board[i][j] == 2) {
				chicken.push_back({ i, j });
			}
		}
	}
	
	dfs(0, 0);

	cout << res;

	return 0;
}

---

코드 설명

1. 도시의 각 칸의 정보를 입력 받는다.

(빠르게 접근하기 위해 집과 치킨집의 위치 정보를 각각 벡터에 저장한다.)

 

2. 백트래킹 탐색을 통해 폐업시키지 않을 치킨집 M개를 선택하고, 해당 정보를 배열에 체크해둔다.

 

3. M개를 선택했을 때, 각 집의 치킨 거리를 계산하고, 합하여 도시의 치킨 거리를 구한다.

 

4. 구한 도시의 치킨 거리 중 최솟값을 출력한다.

---

고찰

처음 문제를 풀 때, 치킨 거리를 BFS로 직접 구하려고 하다가, 메모리 초과 문제가 났다..

 

나는 바보다.

 

제발 문제 좀 잘 읽자!!!