백준 17135번 캐슬 디펜스

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

17135번: 캐슬 디펜스

 

 

 

 

 

<접근방법>

조합, 시뮬레이션 문제입니다.

궁수의 위치를 조합으로 결정한 후, 각각에 대하여 시뮬레이션을 돌리고 최댓값을 찾습니다.

 

적 탐색은 bfs로 하였습니다.

탐색순서를 문제의 조건에 나온 순으로 합니다. 그리고 적을 만나면 저장해주고 탐색을 끝냅니다.

 

/*

(아기상어 문제의 경우 이렇게만 하면 틀립니다. <- 거리 다음 우선순위가 위쪽이라서)

아기상어

https://docs16.tistory.com/38

*/

 

탐색의 방법으로 적과 궁수 사이의 거리를 비교하며 하는 방법도 있습니다.

 

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct point {
	int y, x, d;
};

int n, m, d;
int map[16][16], tmap[16][16];
int a[3];
int res = 0;
int dy[3] = { 0, -1, 0 };
int dx[3] = { -1, 0, 1 };

queue<point> die;

void print() {
	puts("");
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j];
		}
		puts("");
	}
}

void search(int y, int x) {
	queue<point> q;
	int visit[16][16] = {0, };

	q.push({ y, x, 0 });
	visit[y][x] = 1;

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		if (t.d == d + 1) return;

		if (map[t.y][t.x] == 1) {
			die.push({ t.y, t.x });
			return;
		}

		for (int i = 0; i < 3; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];

			if (ty < 0 || ty >= n | tx < 0 || tx >= m) continue;
			if (visit[ty][tx] == 1) continue;

			q.push({ ty, tx, t.d + 1 });
			visit[ty][tx] = 1;
		}

	}
}


void move() {
	queue<point> q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1) {
				map[i][j] = 0;

				if (i + 1 < n) {
					q.push({ i + 1, j });
				}
			}
		}
	}

	//print();

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		map[t.y][t.x] = 1;
	}
}

int kill() {
	int ttres = 0;

	while (!die.empty()) {
		point t = die.front();
		die.pop();

		if (map[t.y][t.x] == 1) {
			map[t.y][t.x] = 0;
			ttres++;
		}
	}
	return ttres;
}

int simul() {
	//맵복사
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			map[i][j] = tmap[i][j];
		}
	}

	int tres = 0;

	for (int z = 0; z < n; z++) {
		for (int i = 0; i < 3; i++) {
			search(n, a[i]);
		}
		tres += kill();

		move();
	}

	return tres;
}

void dfs(int dep = 0, int start = 0) {
	if (dep == 3) {
		res = max(res, simul());
		return;
	}

	for (int i = start; i < m; i++) {
		a[dep] = i;
		dfs(dep + 1, i + 1);
	}

}

int main() {
	cin >> n >> m >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tmap[i][j] = map[i][j];
		}
	}

	dfs();
	cout << res << '\n';
	return 0;
}

 

 

 

 

 

 

---

 

 

<느낀 점>

-지역변수 초기화 생활화 합시다!