15. 3203 : 꿀벌의 여행

DFS문제 

1) 생각할 문제 

-패턴의 시작 위치를 어떻게 결정할 것인가?

-패턴의 시작 위치가 결정되었다면 각 벌들은 패턴의 어느 위치로 이동시킬 것인가?

-이동하는 과정에서 동시에 같은 위치로 이동하게 되면 어떻게 처리할 것인가?

 

2) 시작 위치의 결정

-시작 위치로 결정할 수 있는 범위 (0,0) ~ ( 100 - height, 100 - width )

-위의 범위 중 꿀벌의 위치와 전혀 겹치지 않는 곳은 최적의 결과가 나올 수 없다.

-모든 위치에 대해 최대 이동 꿀벌의 이동거리가 최소인 점을 찾는다.

ㄱ

패턴 범위 지정시 벌에 하나라도 겹치는 것이 유리하다.

 

가장 멀리 가는 벌이 총 이동 시간의 기준이 됨.

 

꽃과 벌이 매칭 가능한 경우의 수 = 7! (5040) 테스트케이스에 따라 부담스러울 수 있는 범위임.

 

백트래킹 기법 사용 필요 : 최소값으로 가지치기. 효율적으로 가지치는 법 : (그림 참조)

이러면 최소값 3이 나오고 3보다 큰 값들은 넘어간다.(가지치기 당함)

 

user.cpp

/// *** user.cpp area start ***

#define MAXBEE     7
#define MAXSIZE  100


// 아래 구조체 선언부는 채점시 주석처리 하고 제출해 주시기 바랍니다.
struct COORD {
	int y, x;
};

COORD start, mybee[MAXBEE], pt[MAXBEE], bs, be, target[MAXBEE];	//리턴값, 꿀벌위치, 패턴위치, 꿀벌의 시작과 끝 좌표, 목표 위치

int N, ansd; //최소이동거리
int order[MAXBEE], num[MAXBEE], chk[MAXBEE];
int map[100][100], dir[7];
const int yy[5] = { 0,0,1,0,-1 };
const int xx[5] = { 0,1,0,-1,0 };
																
/// *** submit area start***

extern int moveBee(int direction[MAXBEE]);
int Min(int x, int y) { return x < y ? x : y; }
int Max(int x, int y) { return x > y ? x : y; }
int Abs(int x) { return x < 0 ? -x : x; }
void init(int B, COORD bee[MAXBEE]) {
	N = B;
	bs.y = bs.x = 100;
	be.y = be.x = 0;
	for (int i = 0; i < N; i++) {
		mybee[i] = bee[i];
		bs.x = Min(bs.x, bee[i].x), be.x = Max(be.x, bee[i].x);
		bs.y = Min(bs.y, bee[i].y), be.y = Max(be.y, bee[i].y);
	}
}
void dfs(int sy, int sx, int n, int maxd) {
	if (maxd >= ansd) return;	//가지치기
	int i, k;
	if (n >= N) {
		ansd = maxd, start.y = sy, start.x = sx;
		for (i = 0; i < N; i++) {
			order[i] = num[i];
		}
	}
	for (i = 0; i < N; i++) {
		if (chk[i]) continue;
		chk[i] = 1;
		num[n] = i;
		k = Abs(pt[i].y + sy - mybee[n].y) + Abs(pt[i].x + sx-mybee[n].x);
		dfs(sy, sx, n + 1, Max(maxd, k));
		chk[i] = 0;
	}

}

void setting(int h, int w) {
	int i, j, k, sy, sx, ey, ex;
	sy = (bs.y + (be.y - h)) / 2, sx = (bs.x + (be.x - w)) / 2;	//중심을 기준으로 하기. 확률적으로 최소값일 확률 높음
	if (sy < 0) { sy = 0; } if (sy > 100 - h) { sy = 100 - h; }
	if (sx < 0) { sx = 0; } if (sx > 100 - w) { sx = 100 - w; }
	for (k = 0; k < N; k++) { chk[k] = 0; }
	dfs(sy, sx, 0, 0);

	sy = Max(0, bs.y - h + 1), sx = Max(0, bs.x - w + 1);
	ey = Min(MAXSIZE - h, be.y), ex = Min(MAXSIZE - w, be.x);

	for (i = sy; i <= ey; i++) {
		for (j = sx; j <= ex; j++) {
			for (k = 0; k < N; k++) {
				chk[k] = 0;
			}
			dfs(i, j, 0, 0);
		}
	}
}
int move(int k) {
	int i, j, flag = 0, ny, nx;
	for (i = 0; i < N; i++) {
		dir[i] = 0;
		for (j = 1; j <= 4; j++) {
			ny = mybee[i].y + yy[i], nx = mybee[i].x + xx[i];
			if (Abs(target[i].y - mybee[i].y) < Abs(target[i].y - ny)) continue;
			if (Abs(target[i].x - mybee[i].x) < Abs(target[i].x - nx)) continue;
			if (map[ny][nx] = k) continue;
			map[ny][nx] = k;
			dir[i] = j;
			mybee[i].y = ny, mybee[i].x = nx;
			flag = 1;
			break;
		}
	}
	return flag;
}
COORD make_pattern(int H, int W, int pattern[MAXSIZE][MAXSIZE]) {
	COORD  result;
	int i, j, k = 0;
	for (i = 0; i < 100; i++) {
		for (j = 0; j < 100; j++) {
			map[i][j] = 0;
		}
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (pattern[i][j]) {
				pt[k].y = i;
				pt[k].x = j;
				k++;
			}
		}
	}
	ansd = 10000;	//넉넉한 값
	setting(H, W);
	for (i = 0; i < N; i++) {
		target[i].y = pt[order[i]].y + start.y;
		target[i].x = pt[order[i]].x + start.x;
	}
	for (k = 1; move(k); k++) {
		moveBee(dir);
	}
	bs = be = start;
	be.y += H - 1, be.x += W - 1;
	return start;
}

 

main.cpp

/// *** main.cpp ***
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include  <stdio.h >

#define MAXBEE             7
#define MAXSIZE          100
#define MAXMOVECOUNT   100000 
static const double ratio = 2.0; // it will be changed

struct COORD {
	int y, x;
};

static COORD bee[MAXBEE];
static int pattern[MAXSIZE][MAXSIZE];
static int width, height, N, M;

static bool okay;
static int movecnt, moveCntLimit;
static int score;
static const int dy[5] = { 0, 0, 1, 0, -1 };
static const int dx[5] = { 0, 1, 0, -1, 0 };

extern void init(int N, COORD bee[MAXBEE]);
extern COORD make_pattern(int height, int width, int pattern[MAXSIZE][MAXSIZE]);

int moveBee(int dir[MAXBEE]) {
	if (!score)
		return score;

	movecnt++;

	if (movecnt > MAXMOVECOUNT)
		return score = 0;

	for (int i = 0; i < N; ++i) {
		if (dir[i] < 0 || dir[i] > 4) {
			return score = 0;
		}

		bee[i].y += dy[dir[i]];
		bee[i].x += dx[dir[i]];

		if (bee[i].y < 0 || bee[i].y >= MAXSIZE || bee[i].x < 0 || bee[i].x >= MAXSIZE)
			return score = 0;
	}

	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N; ++j)
			if (dir[i] * dir[j] > 0 && bee[i].y == bee[j].y && bee[i].x == bee[j].x)
				return score = 0;
	}

	return 1;
}

static bool Matched(COORD start) {
	for (int i = 0; i < N; ++i) {
		int y = bee[i].y - start.y;
		int x = bee[i].x - start.x;

		if (y < 0 || y >= height || x < 0 || x >= width || pattern[y][x] == 0)
			return false;
		--pattern[y][x];
	}
	return true;
}

static void play() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i)
		scanf("%d %d", &bee[i].y, &bee[i].x);

	init(N, bee);

	movecnt = 0;

	for (int i = 0; i < M; ++i) {

		int flower_pattern[MAXSIZE][MAXSIZE] = { { 0 } };

		scanf("%d %d %d", &height, &width, &moveCntLimit);
		for (int y = 0; y < height; ++y) {
			for (int x = 0; x < width; ++x) {
				scanf("%d", &pattern[y][x]);
				flower_pattern[y][x] = pattern[y][x];
			}
		}
		int estimate = movecnt + moveCntLimit * ratio;

		COORD patten_start = make_pattern(height, width, flower_pattern);

		if (movecnt > estimate || !Matched(patten_start))
			score = 0;
		if (score == 0) return;
	}
}

int main() {
	// freopen("input.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	int totalscore = 0;
	for (int t = 1; t <= T; ++t) {
		score = 100;
		play();
		if (score == 0) {
			totalscore = 0;
			break;
		}
		printf("#%d : %d \n", t, movecnt);
		totalscore += score;
	}
	printf("\nscore = %d\n", totalscore);
	return 0;
}