백준 알고리즘 15686_치킨배달 C

문제

(링크)15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

 

사고과정

문제에서 입력이 그래프를 활용할 수 있도록 주어져서 조금 흠칫했다. 하지만 문제에서 요구하는 것은 각 집에서 선택한 치킨집까지의 거리중 최소거리를 합한 것이므로, 각 좌표의 정보를 순차적으로 담기만 하면 된다. 

이후 집의 좌표와 치킨집의 좌표를 따로 저장하고, 재귀함수를 통해 치킨집을 골라내면 된다. 

 

내코드

#include <stdio.h>
#define HOUSE 1
#define CHICKEN 2


typedef struct {
	int x, y;
}Point;

Point house[100];
Point chicken[13];
int house_num = 0, chicken_num = 0;

int abs(int a) {
	if (a < 0)a *= -1;
	return a;
}

int Distance(Point a, Point b) {
	int dx = abs(a.x - b.x);
	int dy = abs(a.y - b.y);
	return dx + dy;
}

void select_chicken(int select[13], int num, int count, int M,int* answer) {
	select[count] = num;
	
	if (count == M-1) {
		int answer_temp = 0;
		for (int i = 0; i < house_num; i++) {
			int min = 10000;
			for (int j = 0; j < M; j++) {
				int dis = Distance(house[i], chicken[select[j]]);
				if (min > dis)min = dis;
			}
			answer_temp += min;
		}
		if (*answer > answer_temp)*answer = answer_temp;
		return;
	}

	for (int i = num + 1; i < chicken_num; i++) {
		select_chicken(select, i, count + 1, M, answer);
	}

}

int main() {
	int N, M,i,j;
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			int n;
			scanf("%d" , &n);
			if (n == HOUSE) {
				house[house_num].x = j;
				house[house_num].y = i;
				house_num++;
			}
			else if (n == CHICKEN) {
				chicken[chicken_num].x = j;
				chicken[chicken_num].y = i;
				chicken_num++;
			}
		}
	}
	int select[13];
	int answer = 10000;
	for (i = 0; i < chicken_num; i++) {
		select_chicken(select, i, 0, M,&answer);
	}

	printf("%d", answer);
	return 0;
}

먼저 abs함수는 절대값을 구하는 함수이고 distance함수와 같이 사용하여 거리의 절대값을 구한다.

Point라는 구조체를 먼저 선언하여 집과 치킨집의 좌표를 저장한다. 이때 house_num과 chicken_num을 증가시켜 최종적인 집과 치킨집의 개수를 구한다. 

select_chicken함수는 치킨집의 번호(index)와 최대 치킨집, 선택한 치킨집 개수 그리고 answer의 주소를 인자로 받는다. select 배열에는 chicken구조체 배열의 index가 저장된다. 이후 현재 저장된 index 이후부터 치킨집을 선택한다. 만약 치킨집을 모두 골랐다면, 각 집에서 가장 가까운 치킨집과의 거리를 구한뒤 temp_answer에 더해준다. temp_answer는 치킨집을 선택한 경우에 따른 거리값이다. 이후 temp_answer와 *answer를 비교하여 다시 *answer를 최솟값으로 갱신한다. 

 

피드백

별로 어려울 것 없는 문제였다. 다만 시간을 줄일 수 있는 방법을 찾아봐야할 것 같다.