[BOJ][백준 15686] 치킨 배달 - C++

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

15686번: 치킨 배달

백준 사이트의 15686번 문제, 치킨 배달 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

치킨 거리란??

• 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.
  도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
  임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
  도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다.
• 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다.
  치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
  시간제한 1초
• 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

---

1. 문제풀이 아이디어

• 어떤 가게를 남길지 경우의 수를 DFS로 구한다.
  최소값을 구하는 것이므로 backtracking으로 경우의 수를 줄인다.
  시간제한이 조금 빡빡하므로 최대한 배열로 풀어보자.
•  
• 1) DFS 돌리며 M개의 치킨집만 남게하고
  2) M개만 남으면 치킨거리 구해주기
•  
• Backtracking 아이디어
  1) 최종 치킨집 개수가 M개 불가능이면 DFS 더 진입하지 않아도된다.

---

2. 코드 핵심 부분

1) 값을 입력받는 input함수,

   보통 input함수를 핵심 부분으로 뽑았을때는 어떤 방식으로 정보를 저장했는지 보면된다.

   아이디어에서 말했듯이 시간제한이 빡빡할 수도 있겠다라는 생각이 들었고,

   문제에서 마침 모든 최대의 개수가 주어져있다.

 

   그래서 구조체나 벡터를 모두 제외하고 이차원 배열만을 활용하여 정보를 저장하였다. 

// 값 입력받는 함수
void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
			// 가정집 정보 저장
			if (Map[i][j] == 1) {
				House[HouseN][0] = i;
				House[HouseN][1] = j;
				HouseN++;
			}
			// 치킨집 정보 저장
			else if (Map[i][j] == 2) {
				Chick[ChickN][0] = i;
				Chick[ChickN][1] = j;
				ChickN++;
			}
		}
	}
}

 

2) 어떤 치킨집을 남길지 고르는 DFS 함수,

   평범한 DFS 틀에서 볼만한 것은 백트래킹을 빡쎄게 했다는것 정도?

// 남길 치킨집 고르는 경우의 수
void dfs(int lv, int Num) {

	// 모든 치킨집 체크했으면 치킨거리 계산
	if (lv == ChickN) {

		int ret = calcDist();

		if (ret < Ans)
			Ans = ret;

		return;
	}

	// 이번 치킨집 남길거면 1, 없앨거면 0, 남긴 치킨집 개수 Num
	for (int i = 0; i < 2; i++) {
		if (i == 0) {
			// 만약 이미 M개 뽑기 불가능이면 갈필요없음
			if (ChickN - lv <= M - Num) 
				continue;
			dfs(lv + 1, Num);
		}
		else {
			// 만약 M개 넘어버렸으면 갈필요없음
			if (Num >= M)
				continue;
			Path[lv] = 1;
			dfs(lv + 1, Num + 1);
			Path[lv] = 0;
		}
	}
}

---

3. 전체 코드

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

using namespace std;

/*
1. 문제읽기
치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.
도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다.

집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다.
치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
시간제한 1초

어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
*/

/*
2. 아이디어
어떤 가게를 남길지 경우의 수를 DFS로 구한다.
최소값을 구하는 것이므로 backtracking으로 경우의 수를 줄인다.
시간제한이 조금 빡빡하므로 최대한 배열로 풀어보자.

1) DFS 돌리며 M개의 치킨집만 남게하고
2) M개만 남으면 치킨거리 구해주기

Backtracking 아이디어
1) 치킨집 개수가 M개 아니면 그냥 안봐도 된다.
*/

// 필요 인자들
int N; // 도시의 크기 (2 ≤ N ≤ 50)
int M; // 남길 치킨집 개수 (1 ≤ M ≤ 13)
int Map[50][50]; // 지도
int ChickN; // 치킨집 개수
int Chick[13][2]; // 치킨집 좌표
int HouseN; // 가정집 개수
int House[100][2]; // 가정집 좌표
int Path[13]; // 남길 치킨집:1, 없어질 치킨집:0
int Ans = 21e8;

// 값 입력받는 함수
void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
			// 가정집 정보 저장
			if (Map[i][j] == 1) {
				House[HouseN][0] = i;
				House[HouseN][1] = j;
				HouseN++;
			}
			// 치킨집 정보 저장
			else if (Map[i][j] == 2) {
				Chick[ChickN][0] = i;
				Chick[ChickN][1] = j;
				ChickN++;
			}
		}
	}
}

// 치킨거리 계산 함수
int calcDist() {
	int Dist = 0;

	// 한집씩 보면서 최소거리 찾아줌
	for (int housei = 0; housei < HouseN; housei++) {
		int Min = 21e8;
		for (int chicki = 0; chicki < ChickN; chicki++) {
			if (!Path[chicki])
				continue;
			int temp = abs(House[housei][0] - Chick[chicki][0]) + abs(House[housei][1] - Chick[chicki][1]);

			if (temp < Min)
				Min = temp;
		}
		Dist += Min;
	}

	return Dist;
}

// 남길 치킨집 고르는 경우의 수
void dfs(int lv, int Num) {

	// 모든 치킨집 체크했으면 치킨거리 계산
	if (lv == ChickN) {

		int ret = calcDist();

		if (ret < Ans)
			Ans = ret;

		return;
	}

	// 이번 치킨집 남길거면 1, 없앨거면 0, 남긴 치킨집 개수 Num
	for (int i = 0; i < 2; i++) {
		if (i == 0) {
			// 만약 이미 M개 뽑기 불가능이면 갈필요없음
			if (ChickN - lv <= M - Num) 
				continue;
			dfs(lv + 1, Num);
		}
		else {
			// 만약 M개 넘어버렸으면 갈필요없음
			if (Num >= M)
				continue;
			Path[lv] = 1;
			dfs(lv + 1, Num + 1);
			Path[lv] = 0;
		}
	}
}

// 메인함수
int main() {

	// input
	input();

	// solve -> DFS 함수 실행
	dfs(0, 0);

	// output
	cout << Ans;

	return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과

골드5 정도의 난이도에 걸맞는 평범한 DFS 문제였다.

요즘 계속 흉악한 구현 문제만 풀다가 이런 문제를 만나니 반가웠다.

 

실행시간도 준수해서 스스로 생각하기에 만족스러운 풀이였다.