6 Problem A : 개미마을3

개미집 한 가구에 1~9마리의 개미가 살고 있고,

이동하는 거리는 마리수와 상관없이,

한 가구가 이동하는 거리만 합산하면 된다

각 개미들의 전체 이동거리를 최소로 하여 모든 대피소에 정원이

초과되지 않도록 대피시키는 프로그램을 작성

 

- 한 층에 대해서 받아서

- 대피소 위치가 3개 이므로 1, 2번의 가운데와 2, 3번의 가운데로 나누어

- 가까운 대피소로 일단 대피시킨다

- 합산을 해서 정원을 초과하는 대피소가 있다면

- 각 마리당 이동 비용을 계산하여

- radix sort를 사용하여 비용기준에 따라 정렬한다

- 그리고 비용이 작은 것부터 초과되지 않도록 이동시킨다

- 마지막에 이동한 후에 다시 수용 가능한 마리를 가진 가구를 이동시킨 후 종료

 

/// === main.cpp ===

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int FLOOR = 10000;

extern void assign(int house[FLOOR][10000]);


static int house[FLOOR][10000];
static int org[FLOOR][10000];
static int shelter[FLOOR][3];



int main(void) {
	srand(3); // The seed will be changed.

	for (register int f = 0; f < FLOOR; f++) // 층 수
	{
		for (register int c = 0; c < 10000; c++) // 열의 수
			org[f][c] = house[f][c] = 1 + (rand() % 9); // 1~9 까지 숫자를 넣음

		for (register int c = 0; c < 3;)
		{
			int r = rand() % 10000;
			if (house[f][r] == 0) continue;

			org[f][r] = house[f][r] = 0; // 대피소에는 0을 입력
			shelter[f][c++] = r; // 각 층에 해당하는 대피소 위치
		}
	}

	int PERFORMANCE = 100000;
	double TOTAL = 0.0;

	time_t start = clock();
	assign(house); // house에 담아 줌 개미들이 가야할 대피소의 위치
	PERFORMANCE -= (clock() - start) / (CLOCKS_PER_SEC / 1000);

	for (register int f = 0; f < FLOOR; f++)
	{
		int sum[3] = { 0, 0, 0 };

		for (register int i, c = 0; c < 10000; c++)
		{
			if (org[f][c] == 0) continue; // 쉘터이면 넘어감
			for (i = 0; i < 3; i++)
				if (house[f][c] == shelter[f][i]) // 이동하기로 한 쉘터가 맞으면
				{
					sum[i] += org[f][c]; // 개미 마리 수 저장

					if (sum[i] <= 20000) TOTAL += abs(shelter[f][i] - c); // c는 열의 위치
					else TOTAL += 10000;

					break;
				}

			if (i == 3) TOTAL += 10000;
		}
	}
	printf("TOTAL = %.10lf , PERFORMANCE = %d\n", TOTAL / 10000 / FLOOR, PERFORMANCE);

	return 0;
}

const int P = (1 << 8); // radix sort 위한 값
int shelter[3], sum[3], sh[10000];
struct data {
	int id, dest, cost;
} ant[20000], tmp[20000];

int Abs(int x) { return x > 0 ? x : -x; }

void r_sort(data *a, data *b, int n) // radix sort, 실제 배열, 임의 배열, 길이
{
	int i, k, cnt[P]; // 
	data *t; // 임시 tmp
	for (k = 0; k < 32; k += 8) { // 32비트를 4분할
		for (i = 0; i < P; i++) cnt[i] = 0; // cnt를 0으로 셋팅하고
		for (i = 0; i < n; i++) cnt[(a[i].cost >> k) & (P - 1)]++; // 갯수 세기
		for (i = 1; i < P; i++) cnt[i] += cnt[i - 1]; // 누적합 구하기
		for (i = n - 1; i >= 0; i--) b[--cnt[(a[i].cost >> k) & (P - 1)]] = a[i]; // 해당 위치에 저장
		t = a; a = b; b = t; // 
	}
}

void move(int s, int house[])
{
	int i, j, cost, an = 0, id, e;
	for (i = 0; i < 10000; i++) { // 모든 개미에 대해서...
		if (sh[i] != s) continue;
		if (s == 1) { // 가운데에서 양옆으로 이동할 때
			cost = (Abs(shelter[0] - i) - Abs(shelter[s] - i)) * 2520 / house[i];
			ant[an++] = { i, 0, cost };
			cost = (Abs(shelter[2] - i) - Abs(shelter[s] - i)) * 2520 / house[i];
			ant[an++] = { i, 2, cost };
		}
		else { // 양끝에서 가운데로 이동할 때
			cost = (Abs(shelter[1] - i) - Abs(shelter[s] - i)) * 2520 / house[i]; // 마리당 가운데로 이동할 때의 추가 비용을 저장
			ant[an++] = { i, 1, cost }; // 현재 위치, 목적지, 비용 저장
		}
	}
	r_sort(ant, tmp, an);
	for (i = 0; i < an && sum[s] > 20000; i++) { // 비용이 적게 드는 것부터 이동시킴
		id = ant[i].id, e = ant[i].dest;
		if (sh[id] != s) continue; // 이미 이동했다면 continue
		if (s == 1 && sum[e] + house[id] > 20000) continue; // 가운데에서 다른 곳으로 이동 하려는데, 이동 전에 20000을 넘으면 이동 안됌, 
		sum[e] += house[id];
		sum[s] -= house[id];
		sh[id] = e;
	}
	for (--i; i >= 0 && sum[s] < 20000; i--) { // 이동한 것에서, 이동하지 않아도 되는 것을 찾는다면 원위치로 이동시킴
		id = ant[i].id, e = ant[i].dest;
		if (sh[id] != e) continue;
		if (sum[s] + house[id] > 20000) continue;
		sum[s] += house[id];
		sum[e] -= house[id];
		sh[id] = s;
	}
}

void proc(int house[10000])
{
	int i, j, k = 0;
	for (i = 0; i < 10000; i++)
		if (house[i] == 0) shelter[k++] = i; // 대피소 위치 저장

	int p1 = (shelter[0] + shelter[1]) / 2, p2 = (shelter[2] + shelter[1]) / 2;  // p1, p2 설정 각 대피소 중간
	for (i = 0; i <= p1; i++) sh[i] = 0;
	for (; i <= p2; i++) sh[i] = 1;
	for (; i < 10000; i++) sh[i] = 2; // 임의 배정
	for (i = 0; i < 3; i++) sh[shelter[i]] = -1, sum[i] = 0; // 실제 대피소 위치는 -1
	for (i = 0; i < 10000; i++) {
		if (sh[i] >= 0) sum[sh[i]] += house[i]; // 임의 배정에 대해 각 개미들을 넣고, 대피소에 들어간 개미 수의 합 계산
	}
	if (sum[0] > 20000) move(0, house);
	if (sum[2] > 20000) move(2, house);
	if (sum[1] > 20000) move(1, house);
	for (i = 0; i < 10000; i++) if (sh[i] >= 0) 
	{ 
		house[i] = shelter[sh[i]]; } // house에 
	return;
}

void assign(int house[10000][10000])
{
	for (register int f = 0; f < 10000; f++)
	{
		proc(house[f]); // 층 마다 문제 해결
	}
}