6 Problem B : 개미마을4

이 차원 배열에서 개미가 대피소로 대피하는 것

 

- 각 개미들이 가장 가까운 곳을 dest 에 저장, 다른 곳으로 이동 했을 때의 차이를 저장

- 저장 할 때 minheap 을 구현하여 저장함

- go : 만약 대피소가 넘치면, 추가 비용을 비교하여 이동시킴

- gogo : 비교이동 한 후 새로운 값을 힙에 대입

- step : 이동 하는 것 구현, 방향, 그리고 다른 개미를 만났을 때 구현

 

#include <stdio.h>
#include <string.h>
#define MAXN 1000

enum { right, down, left, up };

static int N, MoveCount, AnsCount, MaxShelter;
static char MAP[MAXN + 1][MAXN + 1], userMAP[MAXN + 1][MAXN + 1];
static int CNT[MAXN][MAXN];

static int rd[4] = { 0, 1, 0, -1 }, cd[4] = { 1, 0, -1, 0 };

extern void shelter(int N, int M, char userMAP[][MAXN + 1]);

void move(int row, int col, int dir)
{
	MoveCount++;

	if (row < 0 || row >= N || col < 0 || col >= N) return;
	if (MAP[row][col] != 'A') return;
	int nr = row + rd[dir], nc = col + cd[dir];
	if (nr < 0 || nr >= N || nc < 0 || nc >= N) return;
	if (MAP[nr][nc] == 'A') return;
	MAP[row][col] = '0';
	if (MAP[nr][nc] == '0') MAP[nr][nc] = 'A';
	else CNT[nr][nc]++;
}

static void input()
{
	scanf("%d %d %d", &N, &MaxShelter, &AnsCount);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++) CNT[i][j] = 0;
		scanf("%s", MAP[i]);
		strcpy(userMAP[i], MAP[i]);
	}
	MoveCount = 0;
}

int marking()
{
	if (MoveCount > AnsCount) return 1000000;
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
	{		if (MAP[i][j] == 'A' || CNT[i][j] > MaxShelter) return 1000000;
	}
	return MoveCount;
}

int main()
{
	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		input();
		shelter(N, MaxShelter, userMAP);
		printf("#%d : %d\n", i + 1, marking());
	}
	return 0;
}

int hn[3][3];
int sum[3], n, m, map[1010][1010], acnt;

struct SHEL {
	int y, x;
} shel[3];
struct HEAP {
	int id, cost;
} heap[3][3][10010];

int Abs(int x) { return x > 0 ? x : -x; }
void Swap(HEAP &x, HEAP &y) { HEAP z = x; x = y; y = z; }

void push(int s, int e, int p) {
	if (p < 1 || heap[s][e][p / 2].cost <= heap[s][e][p].cost) return; // minheap
	Swap(heap[s][e][p / 2], heap[s][e][p]);
	push(s, e, p / 2);
}

void pop(int s, int e, int p)
{
	int np = p * 2;
	if (np > hn[s][e]) return;
	if (np < hn[s][e] && heap[s][e][np + 1].cost < heap[s][e][np].cost) np++;
	if (heap[s][e][p].cost <= heap[s][e][np].cost) return;
	Swap(heap[s][e][p], heap[s][e][np]);
	pop(s, e, np);
}

struct data {
	int y, x, dist[3], dest;
	void cal(int id) {
		dest = 0;
		for (int i = 0; i < 3; i++) {
			dist[i] = Abs(shel[i].y - y) + Abs(shel[i].x - x);
			if (dist[dest] > dist[i]) dest = i; // 각 쉘터와 거리 중 가장 짧은 거리를 저장
		}
		sum[dest]++; // 가까운 대피소로 이동시켰을 때 들어가는 개미 수 저장
		for (int i = 0; i < 3; i++) {
			if (i == dest) continue;
			heap[dest][i][++hn[dest][i]] = { id, dist[i] - dist[dest] }; 
			// 목적지가 i에서 dest로 바뀌면, 드는 추가 비용 , 각 개미가 가장 가까운 쉘터가 아닌 다른 쉘터로 이동하는데 드는 추가 비용
			push(dest, i, hn[dest][i]);
		}
	}
} ant[10005];
// ant[10005]

extern void move(int row, int col, int dir);

void gogo(int s, int e)
{
	int id = heap[s][e][1].id;
	ant[id].dest = e;
	sum[s]--, sum[e]++;
	for (int i = 0; i < 2; i++) {
		if (i == e) continue;
		heap[e][i][++hn[e][i]] = { id, ant[id].dist[i] - ant[id].dist[e] }; // 새로이 힙에 2개를 넣음
		push(e, i, hn[e][i]);
	}
}

void go(int s)
{
	int e1 = (s + 1) % 3, e2 = (s + 2) % 3, i, j, k;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			if (i == j) continue;
			// 유효한 값인지 확인, 아니면 날리기
			while (ant[heap[i][j][1].id].dest != i) { // 목적지가 i가 아니면
				heap[i][j][1] = heap[i][j][hn[i][j]--]; // 비용이 가장 작은 것 뺴기
				pop(i, j, 1);
			}
		}
	}
	int cost1 = heap[s][e1][1].cost, cost2 = heap[s][e2][1].cost, cost3;
	if (sum[e1] >= m) {
		cost3 = heap[e1][e2][1].cost;
		if (cost1 + cost3 < cost2) { // 2개 이동이 하나 이동보다 작다면
			gogo(e1, e2);
			gogo(s, e1);
		}
		else gogo(s, e2);
	}
	else if (sum[e2] >= m) {
		cost3 = heap[e2][e1][1].cost;
		if (cost2 + cost3 < cost1) { // 2개 이동이 하나 이동보다 작다면
			gogo(e2, e1);
			gogo(s, e2);
		}
		else gogo(s, e1);
	}
	else { // 둘 다 갈 수 있으면, 코스트가 작은쪽으로 이동
		if (cost1 < cost2) gogo(s, e1);
		else gogo(s, e2);
	}
}

int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
void step(int sy, int sx, int ey, int ex)
{
	int dir, ny, nx;
	if (sy == ey && sx == ex) return;
	if (Abs(sy - ey) < Abs(sx - ex)) {
		dir = sx < ex ? 0 : 2; // 방향 설정
	}
	else dir = sy < ey ? 1 : 3; // 방향 설정
	ny = sy + dy[dir], nx = sx + dx[dir]; // 새로운 방향
	int id = map[ny][nx];
	if ((ny != ey || nx != ex) && id < 0) {
		if (dir % 2 == 0) dir = sy < ey ? 1 : 3;
		else dir = sx < ex ? 0 : 2;
		ny = sy + dy[dir], nx = sx + dx[dir];
	}
	if (id > 0) { // 다른 개미를 만나면
		map[ny][nx] = 0;
		step(ny, nx, shel[ant[id].dest].y, shel[ant[id].dest].x);
	}
	move(sy, sx, dir); // main 에서 이동 검증 완료
	step(ny, nx, ey, ex); // user 에서 새로 이동
}

void shelter(int N, int M, char userMAP[][1001])
{
	n = N, m = M, acnt = 0;
	int i, j, k = 0;
	for (i = 0; i < 3; i++) {
		sum[i] = 0;
		for (j = 0; j < 3; j++) hn[i][j] = 0;
	}
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (userMAP[i][j] == 'F') {
				map[i][j] = -1; // shelter 표시
				shel[k++] = { i, j }; // shel 의 좌표 넣기
			}
			else if (userMAP[i][j] == 'A') {
				map[i][j] = ++acnt; // 개미 숫자
				ant[acnt].y = i, ant[acnt].x = j; // 개미 위치 저장
			}
			else {
				map[i][j] = 0;
			}
		}
	}
	for (i = 1; i <= acnt; i++) ant[i].cal(i);
	for (i = 0; i < 3; i++) {
		while (sum[i] > M) go(i);
	}
	for (i = 1; i <= acnt; i++) {
		if (map[ant[i].y][ant[i].x] == 0) continue;
		map[ant[i].y][ant[i].x] = 0;
		step(ant[i].y, ant[i].x, shel[ant[i].dest].y, shel[ant[i].dest].x);
	}
}

1 10 4 34 00000000A0 0A00000000 000F00A000 0000000000 00A00A0000 0000000000 000000A0F0 A00000000A 00000F00A0 000A000000

34