[BOJ-17135] 캐슬 디펜스 문제 풀이

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

17135번: 캐슬 디펜스

 

시뮬레이션 문제입니다.

 

매번 dfs, bfs 문제만 풀다가 처음으로 시뮬레이션 문제를 풀어봤습니다.

 

일단 문제 풀이에 앞서, 제가 이 문제를 풀 때 접근했던 생각 4가지를 공유해드리겠습니다.

 

1. 적의 위치 정보를 따로 저장했습니다.

-> 따로 저장해두지 않으면 적의 위치를 찾는 것부터해서 탐색 시간이 길어질 것 같았습니다.

 

2. 궁수 3명을 각각 다른 위치에 배치하는 경우를 백트래킹으로 구현했습니다.

-> for문을 여러개 사용하는 방법도 있지만, 배운 사람이기 때문에 이렇게 구현했습니다 ^^;;

 

3. 한 턴이 끝나고 적이 내려올 때 코드가 길어질 것 같아, 적이 아래로 내려오는 함수를 만들어야 겠다고 생각했습니다.

(여기서 성에 닿았을 경우를 함께 고려해줬습니다.)

-> 적이 내려오는 것까지 작성하면 안그래도 코드의 가독성이 떨어지는데... 더 떨어질까봐 함수로 만들었습니다..

 

4. 가장 많은 적을 제거했을 경우를 구하는 문제이기 때문에 완전 탐색을 해야하기 때문에, 궁수의 위치가 0~m까지 변할 때 마다 처음의 map을 다시 가져와서 사용해야 해서 map을 백업하는 함수를 따로 만들어 줬습니다.

 

이 4가지 사항을 고려하여 코드를 작성하겠다고 생각했고 문제에서 하라는 대로 구현만 해줬습니다.

 

난이도는 어려운 수준은 아니었던것 같습니다.

-----------------------------------------------------------------------------------------------------------------------------------

 

프로그램의 작동 순서는 아래와 같습니다.

 

1. 필드의 정보를 입력 받습니다. -> 여기서 적의 위치를 따로 저장합니다.

 

2. 궁수와 가장 가까운 적의 거리를 저장할 배열, 위치를 저장할 배열을 infinite값(0x7fffffff)으로 초기화 해줍니다.

(가장 가까운 거리와 거리가 같은 적이 존재할 경우 x좌표가 작은 적을 제거하기 위해 가장 큰 값으로 초기화 했습니다.)

 

3. 궁수 3명을 0번 부터 차례로 배치시키고 시작합니다.

 

  3-1. 3명의 궁수를 배치시켰을 때, map을 미리 백업해 둡니다.

 

  3-2. 적이 존재할 경우 계속 반복하여 현재 궁수의 위치에 대한 모든 적의 거리를 구하고 가장 가까운 적을 선택합니다.

 

  3-3. 적을 제거하고, 제거한 적을 count 해줍니다.

   -> 이 과정에서 저는 같은 적을 제거하는 경우를 함께 고려해서 코드를 작성했습니다. (제거한 적을 0으로 만들어버리면 다음에 count를 하지 않도록 했습니다.)

 

  3-4. 적을 1칸씩 내려보냈습니다.

-----------------------------------------------------------------------------------------------------------------------------------

아래는 소스 코드입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

struct POINT {
	int y, x;
};
int n, m, d, ret;
int map[16][15];
int enemy_cnt;
vector<POINT> vec, pick, xpick;
int arr[3];
int arrx[3], arry[3];
bool visited[16][15];

void copy_map(int desc[16][15], int src[16][15]) {
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			desc[y][x] = src[y][x];
		}
	}
}

void move_down() {

	for (int y = n - 1; y >= 0; y--) {
		for (int x = 0; x < m; x++) {
			if (map[y][x] == 1) {
				map[y][x] = 0;
				if (y + 1 != n) {
					map[y + 1][x] = 1;
					vec.push_back({ y + 1, x });
				}
			}
		}
	}
}

void dfs(int index) {
	if (pick.size() == 3) {	//궁수의 위치를 3개 골랐으면 true
		int candi = 0;	//제거할 수 있는 적의 수에 대한 후보
		int backup[16][15];	//현재 필드 상태를 저장할 백업 데이터
		copy_map(backup, map);	//현재 필드 상태를 백업해둠.

		while (vec.size()) {	//적이 존재하면 반복
			for (int c = 0; c < pick.size(); c++) {	//모든 궁수가
				for (int i = 0; i < vec.size(); i++) {	//모든 적에 대해서 반복
					int dist = abs(pick[c].x - vec[i].x) + abs(pick[c].y - vec[i].y);	//한 궁수에 대해 모든 적과의 거리를 저장
					if (dist <= d) {	//거리가 d 이하일 경우
						if (dist < arr[c]) {	//현재 가장 가까운 적과의 거리보다 dist가 작다면
							arr[c] = dist, arrx[c] = vec[i].x, arry[c] = vec[i].y;	//현재 가장 가까운 적과의 거리는 dist이고 그 적의 위치는 arrx,arry에 저장
						}
						else if (dist == arr[c]) {	//만약 현재 가장 가까운 적과의 거리와 dist가 같다면
							if (vec[i].x < arrx[c]) {	//x 좌표를 비교해서 현재 가장 가까운 적의 x좌표보다 vec의 x좌표가 작다면
								arrx[c] = vec[i].x, arry[c] = vec[i].y;	//현재 좌표 정보를 갱신 
							}
						}
					}
				}
			}	//arr[], arrx[], arry[]에는 가장 가까운 적들의 위치, 거리 정보가 들어옴

			for (int i = 0; i < 3; i++) {
				if (arrx[i] == 0x7fffffff) continue;
				if (map[arry[i]][arrx[i]] == 1) {
					map[arry[i]][arrx[i]] = 0;
					candi += 1;
				}
				arr[i] = 0x7fffffff, arrx[i] = 0x7fffffff, arry[i] = 0;	// 다음 적에 대한 정보를 받기 위해 초기화
			}	//적 제거

			if (ret < candi) ret = candi;

			while (vec.size()) {
				vec.pop_back();
			}

			move_down();	//적 1칸 내려옴
			memset(visited, false, sizeof(visited));
		}

		copy_map(map, backup);
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++) {
				if (map[y][x] == 1) {
					vec.push_back({ y,x });
				}
			}
		}
		return;
	}

	//궁수의 위치(겹치지 않고)를 받는 경우의 수
	for (int i = index; i < m; i++) {
		pick.push_back({ n, i });	//pick은 y좌표(n으로 고정)와 x좌표를 받는다.
		dfs(i + 1);	//현재 위치(i)의 다음 위치를 매개변수로 받는다.
		pick.pop_back(); //3개의 위치를 받고나서 적을 제거하고 다시 돌아와서 제일 마지막에 받은 위치를 pop
	}
}

int main(void) {

	scanf("%d %d %d", &n, &m, &d);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			scanf("%d", &map[y][x]);
			if (map[y][x] == 1) {
				vec.push_back({ y,x });
			}	//적인 경우 vec에 추가(적의 위치를)
		}
	}

	arr[0] = 0x7fffffff, arrx[0] = 0x7fffffff;	//궁수가 올 수 있는 자리(arrx)와 
	arr[1] = 0x7fffffff, arrx[1] = 0x7fffffff;	//현재 궁수와 가장 가까운 적 까지의 거리를 저장(arr)
	arr[2] = 0x7fffffff, arrx[2] = 0x7fffffff;	//를 초기화.

	dfs(0);	//0의 위치부터 궁수를 배치시키기 위해 매개변수로 0을 줌

	printf("%d\n", ret);

	getchar();
	getchar();

	return 0;
}

 

첫 문제 풀이어서 장황하게 느껴질거라 생각합니다.

 

혹시 이해가 안가시는 부분이 있다면 댓글로 남겨주시면 즉각 피드백 해드리겠습니다!