[C] 백준 15686번 치킨 배달

 

안녕하세요 (╹ڡ╹ ),,

오늘은 오랜만에 백준 문제를 풀어보았습니다!

백준 15686번

15686번: 치킨 배달

 

우선 이번 문제에서는 N (50 이하)과 M (13 이하)이 모두 작은 수로 주어졌기 때문에

브루트 포스로 푸는 것이 가장 적합할 것 같다고 생각했습니다!

문제는 총 4단계에 걸쳐 해결하였습니다.

 

---

 

1. 입력받은 도시 정보에서 집과 치킨집을 구분하기

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

입력으로 들어온 값을 보면 위의 2차원 형식과 같이 전체 도시 정보가 입력됨을 알 수 있습니다.

저는 구현을 조금 더 간단하게 하기 위해 집과 치킨집의 좌표값만 따로 저장을 하였습니다.

• 0: 빈칸 (저장 x)
• 1: 집
• 2: 치킨집

---

2. 전체 치킨집 중 M개의 치킨집을 고르기 (나머지는 폐업)

우리는 전체 치킨집 중 M개의 치킨집만 선택한 후 나머지는 모두 폐업해야 합니다.

전체 치킨집의 개수를 K개라고 했을 때, 우리는 이를 combination(K, M)으로 생각할 수 있습니다.

(=K개 중에 서로 다른 M개 선택하기)

 

combination은 재귀함수를 사용하면 쉽게 구현할 수 있습니다.

먼저 combination 함수의 종료 조건부터 생각을 해보면

1. 선택한 치킨집이 M개 일 때

2. 전체 치킨집을 모두 탐색하였을 때

가 있을 수 있습니다.

 

combination 함수에서는 치킨집을 처음부터 하나씩 탐색해가면서,

해당 치킨집을 선택하는 경우 / 선택 안 하는 경우를 모두 호출합니다.

코드를 대충 간소화 해보면 아래와 같습니다.

Function combination(선택여부)
    if 탐색한 치킨집 == M then return;
    if 탐색한 치킨집 == K then return;
    combination(선택);
    combination(선택x);

---

 

3. 각 집의 치킨 거리 계산하기

각 집의 치킨 거리는 combination 함수가 특정 조건에서 종료할 때 실시를 하면 됩니다.

해당 조건은 K개의 치킨집 중 M개를 성공적으로 선택했을 때입니다. (M개를 선택하지 못하고 종료할 때는 고려 x)

1번에서 별도로 저장해둔 집의 좌표 배열과 선택한 치킨집 배열을 for문으로 탐색해가면

각 집에서 가장 가까운 치킨집의 거리를 구할 수 있습니다.

---

 

4. 도시의 치킨 거리 계산하기

도시의 치킨 거리는 3번을 계산하면서 모든 집의 치킨 거리를 더했을 때

가장 작은 치킨 거리 합을 가진 케이스를 구하면 됩니다.

---

 

이를 바탕으로 작성한 코드는 아래와 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, M;
typedef struct map {
	int x, y;
}map;
map house[100], chicken[13], choosed_chicken[13];
int house_idx = -1, chicken_idx = -1;
int min = 50 * 2 * 50;

// (3번) 집과 치킨집 사이의 치킨 거리 계산
int gap(map a, map b) {
	int gap = 0;
	gap = a.x > b.x ? a.x - b.x : b.x - a.x;
	gap += a.y > b.y ? a.y - b.y : b.y - a.y;
	return gap;
}

// (4번) 도시의 치킨 거리 계산
void calculate() {
	int distance = 0, sum = 0;
	for (int i = 0; i <= house_idx; i++) {
		int chicken_distance = 50 * 2;
		for (int j = 0; j < M; j++) {
			distance = gap(house[i], choosed_chicken[j]);
			if (distance < chicken_distance)
				chicken_distance = distance;
		}
		sum += chicken_distance;
	}
	if (sum < min)
		min = sum;
}

// (2번) chicken_idx개의 치킨집 중에 M개만 고르기
/* 
depth: 몇 번 index를 보고 있는지
cnt: 현재 선택된 치킨집의 개수
isChoose: 해당 index의 치킨집을 선택할지 안할지
*/
void choose(int depth, int cnt, int isChoose) {

	if (isChoose == 1)
		choosed_chicken[cnt - 1] = chicken[depth];

	if (M == cnt){
		calculate();
		return;
	}
	if (depth == chicken_idx)
		return;

	choose(depth+1, cnt+1, 1);
	choose(depth+1, cnt, 0);
}

int main()
{
	scanf("%d%d", &N, &M);
	int input;
       // (1번) 집과 치킨집 구분하기
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			scanf("%d", &input);
			if (input == 1) {
				house_idx += 1;
				house[house_idx].x = i;
				house[house_idx].y = j;
			}
			else if (input == 2) {
				chicken_idx += 1;
				chicken[chicken_idx].x = i;
				chicken[chicken_idx].y = j;
			}
		}

	choose(-1, 0, -1);

	printf("%d\n", min);
	return 0;
}

choose() 함수를 통해 최종적으로 구한 M개의 치킨집은 choosed_chicken이라는 배열에 따로 저장을 해두었습니다. 

(계산의 용이함을 위해,,)

그리고 초기 choose 함수 인자로 (-1, 0, -1)로 사용하여 아직 아무것도 choose하지 않은 초기 상황을 표현하였습니다.

 

코딩 문제는 늘 꾸준히 자주 풀어야지 하는데

개강하고부터는 시간이 없어서 ㅠㅠ 맨날 뒷전이네요 ...

 

오늘도 방학되면 열심히 해야지 ~,, 라는 마음을 품으며 .. ★