[백준] 15686번: 치킨 배달

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

15686번: 치킨 배달

문제 이해

시간 초과 때문에 조금 애먹었던 문제이다.

심지어 처음에 너무 어렵게 접근해서 무슨 DFS + BFS로 풀었다... -> 당연 시간 초과

치킨집과 집 간의 거리는 그냥 수식으로 계산해야한다.

 

그리고 이걸 순열로 풀면 시간초과에 걸린다. 반드시 조합으로 해야한다.

이걸 알면서도 나는 순열로 풀고 있었다. ㅎㅎ...

DFS에 idx를 추가해서 순열로 바꿔줬더니 바로 통과되었다. 

 

결론은, 그냥 치킨 집이 13개니까 이걸 기준으로 DFS를 돌리면 된다. 

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 50
#define ABS(x) (((x)>0)? (x): -(x))
int N, M;
int map[MAXN+2][MAXN+2];
int visited[MAXN+2][MAXN+2];
typedef struct st {
	int y, x;
}ELE;
ELE house[MAXN * MAXN + 1];
ELE chicken[13 + 1];
int sel[13 + 1];

int hcnt, ccnt;
int min_dis = 0x7fffffff;

void Get_Input(void) {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) { // 집
				house[hcnt].y = i, house[hcnt++].x = j;
			}
			if (map[i][j] == 2) {
				chicken[ccnt].y = i, chicken[ccnt++].x = j;
			}
		}
	}
}

int Get_Chicken_Distance(void) {
	int sum = 0;
	for (int i = 0; i < hcnt; i++) {
		int min = 0x7fffffff;
		for (int j = 0; j < M; j++) {
			int dis = ABS(chicken[sel[j]].y - house[i].y) + ABS(chicken[sel[j]].x - house[i].x);
			if (min > dis) min = dis;
		}
		sum += min;
	}
	return sum;
}

void DFS(int cnt, int idx) {
	// 종료
	if (cnt == M) {
		int res = Get_Chicken_Distance();
		if (res < min_dis) min_dis = res;
		return;
	}

	// 재귀
	for (int i = idx; i < ccnt; i++) {
		sel[cnt] = i;
		DFS(cnt + 1, i+1);
	}
}

int main(void) {
	Get_Input();
	// M개의 치킨 집을 고르고, 거기까지의 치킨 거리 구하기
	DFS(0, 0);
	printf("%d", min_dis);
	return 0;
}