BOJ 17135 : 캐슬 디펜스 (A형 상시)

삼성 A형 전체 링크

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/17135

 

 

먼저 궁수가 탐색해야할 우선순위를 구해보자.

아래의 그림은 D = 1, 2, 3인 경우 궁수가 탐색해야하는 순서다.

적이 가장 가까울 경우 가장 왼쪽에 있는 적을 공격한다고 하였으므로, 

거리가 가장 가까운 앞을 보고, 그 다음 거리부터는 왼쪽/가운데/오른쪽 순서대로 탐색한다.

 

D = 4인 경우, 규칙이 점점 보인다.

 

위의 탐색 순서를 궁수를 기준으로 r, c로 나타내면 아래와 같다.

 

좌표 r은 -1부터 시작해서 감소하다가 다시 증가한다.

좌표 c는 처음엔 0이며, 그 다음 주기에는 -1 부터 1씩 증가, 그 다음은 -2부터 1씩 증가한다.

이 주기는 D = 4일 때, 1, 1 ~ 3, 1 ~ 5, 1 ~ 7로 나누면 규칙이 보이게 된다.

 

먼저, D는 최대 10이므로 좌표 (r, c)의 구조체를 11개 이상 선언한다.

그리고 각 D마다 index를 관리하기 위해 정수 배열도 정의한다.

#define MAX (15 + 5)

typedef struct st
{
	int r;
	int c;
}RC;

RC priority[10 + 2][MAX * MAX];
int pcnt[10 + 2];

 

위의 규칙대로 보면 D = 4일 때, 탐색해야할 개수는 4² = 16이다.

따라서 각 D마다 10 * 10 이상의 값으로 선언하면 된다. 여기서는 간단히 MAX의 제곱으로 선언하였다.

 

먼저 1 → 1, 2, 3 → 1, 2, 3, 4, 5로 r, c의 규칙이 2씩 증가하므로, time = 1로 정의하고 매번 +2씩 증가시킨다.

sr은 (1) / (1, 2, 1) / (1, 2, 3, 2, 1)의 규칙을 가진다.

즉, 1부터 시작하고 +flag(1)을 해준 후, time / 2 회차부터는 flag를 -1로 바꿔 감소시킨다.

sc의 경우는 1번 loop에서 -1부터 시작하고, 2번 loop에서 -2, N번 loop에서 -N부터 시작해서 1씩 증가한다.

/* priority */
for (int d = 1; d <= 10 /* D */ ; d++)
{
	int time = 1;
	for (int i = 0; i < d; i++) /* D번 반복*/
	{
		int sc, sr, flag;

		sr = 1; sc = -i;
			
		flag = 1;
		for (int t = 1; t <= time; t++)
		{
			priority[d][pcnt[d]].r = sr * -1;
			priority[d][pcnt[d]++].c = sc;

			sc++;
			sr += flag;
			if (t == time / 2) flag = -1;
		}
	
		time += 2;
	}
}

모든 거리에 대해 우선순위를 구할 필요는 없지만, 제대로 만들었는지 확인하기 위해 전체를 debug해보자.

 

아래 print 코드를 넣어서 D = 1 ~ 10까지 우선순위 탐색 좌표가 제대로 구현되었는지 출력해보자.

// D = 1 ~ 10;
for (int i = 0; i < pcnt[D]; i++) printf("%d ", priority[D][i].r);
putchar('\n');
for (int i = 0; i < pcnt[D]; i++) printf("%d ", priority[D][i].c);
putchar('\n');

---

궁수가 탐색해야하는 우선순위가 정해졌으므로, 궁수를 배치한다.

궁수를 배치하는 조합은 N과 M (2) - 조합을 참고하면 된다.

archer 배열의 0번 배열부터 궁수의 위치를 저장한다.

 

N = 5인 경우 궁수가 있어야 할 column의 좌표는 아래와 같다.

 

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

 

경우의 수를 만들때는 꼭 출력해서 제대로 경우의 수가 만들어지는지 확인하자. (outputArcher)

int archer[MAX];

void outputArcher()
{
	for (int i = 0; i < 3;i++) printf("%d ", archer[i]); 
	putchar('\n'); 
}

int MAXANS = 0;
void DFS(int L, int start)
{
	if (L == 3)
	{
		//outputArcher();
		int tmp = simulate();
		if (MAXANS < tmp) MAXANS = tmp;
		
		return;
	}

	for (int i = start; i <= M; i++)
	{
		archer[L] = i;
		DFS(L + 1, i + 1);
	}
}

 

궁수는 최대 3명 배치할 수 있으므로 L = 3에서 DFS를 종료하고, 시뮬레이션을 한다.

적들을 1칸씩 내리는 것보다 궁수를 1칸씩 올리는 것이 더 구현하기 편하다.

---

simulate 함수는 궁수가 제거한 적의 수를 return한다. simulate는 아래와 같이 구현한다.

 

1) init, MAP을 복사하고, 사정거리 D를 보고 priority 배열을 가져온다. priority 개수도 가져온다.

2) 궁수를 row = N + 1부터 2까지 위로 이동시킨다. (1까지 옮겨도 상관없지만 제거할 적이 없으므로 의미가 없다.)

3) 궁수 3명을 for문을 돌면서 적을 탐색한다. 적이 탐색되면 break로 빠져나간다.

4) 궁수가 동시에 하나의 적을 제거하는 경우가 있으므로, dead에 제거할 후보를 저장한다.

5) dead를 보고 MAP을 지운다. 이 때, MAP[r][c] = 1인 경우만 count한다.

   dead에 좌표가 있지만 MAP[r][c]가 0인 경우는 앞의 궁수가 이미 제거를 한 경우가 된다.

int simulate()
{
	/* 1) */
	int tmpMAP[MAX][MAX] = { 0 };
	RC* archer_priority = priority[D];
	int apcnt = pcnt[D];
	
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			tmpMAP[r][c] = MAP[r][c];

	int enemy = 0;
	for (int r = N + 1; r >= 2; r--) /* 2) */
	{
		RC dead[3] = { 0 };
		int dcnt = 0;

		for (int a = 0; a < 3; a++) /* 3) */
		{
			int ar, ac;

			/* archer의 위치 */
			ar = r;
			ac = archer[a];

			for (int p = 0; p < apcnt; p++)
			{
				int nr, nc;

				nr = ar + archer_priority[p].r;
				nc = ac + archer_priority[p].c;
	
				if (nr < 1 || nc < 1 || nr > N || nc > M) continue;

				if (tmpMAP[nr][nc]) /* 4) */
				{
					dead[dcnt].r = nr;
					dead[dcnt++].c = nc;

					break; /* 적 1명 제거 시 종료 */
				}
			}
		}

		for (int d = 0; d < dcnt; d++) /* 5) */
		{
			int r = dead[d].r;
			int c = dead[d].c;

			if (tmpMAP[r][c])
			{
				tmpMAP[r][c] = 0;
				enemy++;
			}
		}
	}

	return enemy;
}

 

DFS에서 시뮬레이션이 종료되면 MAXANS를 갱신하면 된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (15 + 5)

int N, M, D;
int MAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}RC;

RC priority[10 + 2][MAX * MAX];
int pcnt[10 + 2];

int archer[MAX];

void input()
{
	scanf("%d %d %d", &N, &M, &D);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);

	/* priority */
	//for (int d = 1; d <= D; d++)
	{
		int time = 1;
		for (int i = 0; i < D; i++) /* D번 반복*/
		{
			int sc, sr, flag;

			sr = 1; sc = -i;
			
			flag = 1;
			for (int t = 1; t <= time; t++)
			{
				priority[D][pcnt[D]].r = sr * -1;
				priority[D][pcnt[D]++].c = sc;

				sc++;
				sr += flag;
				if (t == time / 2) flag = -1;
			}
	
			time += 2;
		}
	}

	//for (int i = 0; i < pcnt[D]; i++) printf("%d ", priority[D][i].r);
	//putchar('\n');
	//for (int i = 0; i < pcnt[D]; i++) printf("%d ", priority[D][i].c);
	//putchar('\n');
}

int abs(int a)
{
	return a > 0 ? a : -a;
}

int getLength(int r1, int r2, int c1, int c2)
{
	return abs(r1 - r2) + abs(c1 - c2);
}

void outputArcher()
{
	for (int i = 0; i < 3;i++) printf("%d ", archer[i]); 
	putchar('\n'); 
}

int simulate()
{
	/* 1) */
	int tmpMAP[MAX][MAX] = { 0 };
	RC* archer_priority = priority[D];
	int apcnt = pcnt[D];
	
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			tmpMAP[r][c] = MAP[r][c];

	int enemy = 0;
	for (int r = N + 1; r >= 2; r--) /* 2) */
	{
		RC dead[3] = { 0 };
		int dcnt = 0;

		for (int a = 0; a < 3; a++) /* 3) */
		{
			int ar, ac;

			/* archer의 위치 */
			ar = r;
			ac = archer[a];

			for (int p = 0; p < apcnt; p++)
			{
				int nr, nc;

				nr = ar + archer_priority[p].r;
				nc = ac + archer_priority[p].c;
	
				if (nr < 1 || nc < 1 || nr > N || nc > M) continue;

				if (tmpMAP[nr][nc]) /* 4) */
				{
					dead[dcnt].r = nr;
					dead[dcnt++].c = nc;

					break; /* 적 1명 제거 시 종료 */
				}
			}
		}

		for (int d = 0; d < dcnt; d++) /* 5) */
		{
			int r = dead[d].r;
			int c = dead[d].c;

			if (tmpMAP[r][c])
			{
				tmpMAP[r][c] = 0;
				enemy++;
			}
		}
	}

	return enemy;
}

int MAXANS = 0;
void DFS(int L, int start)
{
	if (L == 3)
	{
		outputArcher();
		int tmp = simulate();
		if (MAXANS < tmp) MAXANS = tmp;
		
		return;
	}

	for (int i = start; i <= M; i++)
	{
		archer[L] = i;
		DFS(L + 1, i + 1);
	}
}

int main(void) 
{
	input();
	
	DFS(0, 1);

	printf("%d\n", MAXANS);
	
	return 0;
}