BOJ, 백준) 17135 캐슬디펜스 ( C / C++)

1. 문제 링크

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

17135번: 캐슬 디펜스

2. 문제 개요

Board의 맨 밑줄에 적절히 궁수를 두어 몬스터를 가장 많이 잡을 수 있는 경우를 찾는 것.

 

3. 문제 힌트 -> 보고 한번더 풀어보세요!

적절히 궁수를 두는 방법 : Brute force -> DFS

궁수를 둔 뒤 사정거리를 체크하는방법 -> BFS

목표물을 찾고 바로 삭제하지말고 모든 궁수들이 목표물을 지정한 뒤 한꺼번에 삭제하기

 

4. 문제 풀기

우선 최선의 결과를 얻기 위해서는 Brute force로 모두 계산해 보아야 한다.

그래서, DFS를 통해서 궁수들의 자리를 지정하고, BFS 및 다른 구현을 통해서 시뮬레이션을 해본다.

그 후 가장 좋은 결과를 출력하는방법.

 

궁수가 놓일 수 있는방법은 순열로 구할 수 있다.

Simulation을 하기 위해 맵을 복사할 함수를 정의 해놓고 BFS를 돌려 Targeting을 한다.

주의할 점은 1번궁수가 몬스터가 사정권 안에 있다고 바로 삭제해서는 안된다는 것이다.

3명의 궁수들 모두 BFS를 돌리면 궁수 1명당 1마리의 몬스터를 지정하게 된다. ( 사냥하게 될 )

 

1번 궁수와 2번 궁수가 잡고자 하는 몬스터가 동일 할 수 있으므로 한꺼번에 처리하도록 하고,

2번궁수가 몬스터를 잡을때 방금 1번이 잡은 몬스터는 아닌지 Check 할 필요가 있다.

 

그 뒤 몬스터를 한칸 내린다.

이런 흐름이 계속 반복되는 구조이다.

 

5. 코드

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int n, m, d;
int map[15][15];
int order[3];
int monster = 0;
int ret = -1;
struct COORD {
	int y, x;
	int time;
};
const int dx[] = { -1,0,1,0 };
const int dy[] = { 0,-1,0,1 };

void cpmap(int dest[][15], int src[][15])
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dest[i][j] = src[i][j];
	return;
}

void dfs(int depth, int start)
{
	if (depth == 3)
	{
		int kill = 0;
		int monsternum = monster;
		int clone[15][15] = { 0 };
		cpmap(clone, map);

		while (monsternum != 0)
		{
			vector<COORD> target;
			for (int i = 0; i < 3; i++)
			{
				queue<COORD>q;
				bool visited[15][15] = { false, };
				COORD s;
				s.y = n, s.time = 0;
				s.x = order[i], q.push(s);
				bool isfind = false;
				while (!q.empty())
				{
					COORD cur = q.front(); q.pop();

					for (int dir = 0; dir < 4; dir++)
					{
						COORD next;
						next.x = cur.x + dx[dir];
						next.y = cur.y + dy[dir];
						next.time = cur.time + 1;
						if (next.x < 0 || next.y < 0 || next.x >= m || next.y >= n
							|| next.time > d)
							continue;

						if (visited[next.y][next.x] == false)
						{
							if (clone[next.y][next.x] == 1)
							{
								target.push_back(next);
								isfind = true;
								break;
							}
							visited[next.y][next.x] = true;
							q.push(next);
						}
					}
					if (isfind)break;
				}
			}
			//targeting end.
			int len = target.size();
			for (int i = 0; i < len; i++)
			{
				if (clone[target[i].y][target[i].x] == 1)
				{
					clone[target[i].y][target[i].x] = 0;
					kill++;
					monsternum--;
				}
			}
			
			//monster moving
			for (int j = 0; j < m; j++) {
				if (clone[n - 1][j] == 1)
					monsternum--;

				for (int i = n - 1; i > 0; i--)
					clone[i][j] = clone[i - 1][j];
				clone [0][j] = 0;
			}
		}
		ret = max(ret, kill);
		return;
	}
	for (int i = start; i < m; i++)
	{
		order[depth] = i;
		dfs(depth + 1, i + 1);
	}

	return;
}
int main(void)
{
	scanf("%d %d %d", &n, &m, &d);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1)	monster++;
		}
	
	//combination
	dfs(0, 0);
	
	printf("%d", ret);
	return 0;
}

 

6. 결과 사진

7. TAG

   #백준 번호  #백준 제목 # 번호 제목 

 

지적, 댓글 언제나 환영입니다~