[C++] 백준 17135 캐슬디펜스

문제 링크

---

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

접근 방법

---

 설계만 잘한다면 어렵지 않게 풀 수 있는 문제였습니다.

 

1. 궁수가 3명 필요하므로 3명을 세울 수 있는 조합을 모두 찾는다.

2. 조합이 완성되었을 때, 궁수 각자의 표적을 찾는다.

3. 표적을 제거 후 다음 턴을 진행한다.  

 

1. 궁수가 3명 필요하므로 3명을 세울 수 있는 조합을 모두 찾는다.

void comb(int cnt, int start, vector<int> &archers) {
	if (cnt == 3) {
		int result = 0;
		copyTmp();
		for (int i = 0; i < n; i++) {
			result += thisTurn(archers);
		}
		ans = max(ans, result);
		return;
	}
	for (int i = start + 1; i < m; i++) { //m이 가로 길이
		archers.push_back(i);
		comb(cnt + 1, i, archers);
		archers.pop_back();
	}
}

backtracking을 사용하며 가능한 모든 궁수 3명의 조합을 찾을 수 있습니다.

조합이 완성되면 게임을 진행하며 총 몇명의 적(result)이 제거 되었는지 카운트 합니다.

thisTurn()은 한 턴에서 제거된 적을 계산하며, 한 게임은 세로길이는 n턴이 지나야 게임이 끝나므로 n번 반복합니다.

 

2. 조합이 완성되었을 때, 궁수 각자의 표적을 찾는다.

int thisTurn(vector<int> &archers) {

	int cnt = 0;

	vector <pair<int, int>> targets;
	for (int i = 0; i < archers.size(); i++) {
		pair<int, int> target = decideTarget(archers[i]);
		if (target.first != 999 && target.second != 999) {
			targets.push_back(target);
		}
	}
	for (int i = 0; i < targets.size(); i++) {
		pair<int, int> target = targets[i];
		if (tmp[target.first][target.second] == 1) {
			tmp[target.first][target.second] = 0;
			cnt++;
		}
	}

	for (int i = n - 2; i >= 0; i--)
		for (int j = 0; j < m; j++) 
			tmp[i + 1][j] = tmp[i][j];
	for (int j = 0; j < m; j++)
		tmp[0][j] = 0;

	return cnt;
}

궁수 한명의 표적을 찾는 일은 decideTarget()에서 진행됩니다. 제거할 모든 적을 vector<pair<int, int>> targets에 저장한 뒤 적을 제거하며 cnt를 카운트합니다. 이렇게 한턴이 종료 되면 적들을 한칸 씩 밑으로 이동 시킵니다.

 

3. pair<int, int> decideTarget(int archer)

pair<int, int> decideTarget(int archer) {
	
	bool visited[15][15] = { false };
	pair<int, int> nextdir[3] = { {-1,0}, {0,1}, {0,-1} };
	pair<int, int> ret = { 999, 999 };
	queue<coord> q;
	int dist = 999;

	q.push({ n - 1, archer, 1 });

	while (!q.empty()) {

		coord now = q.front();
		q.pop();

		if ((dist != 999 && dist < now.dist) || now.dist > d) //이미 표적을 잡았는데 더 멀리 갈때, 공격 범위를 벗어 낫을 때
			break;

		if (tmp[now.x][now.y] == 1) {
			if (dist >= now.dist) {
				dist = now.dist;
				if(ret.second > now.y) //기존 표적보다 더 왼쪽에 있을 때
					ret = { now.x, now.y };
			}
		}

		for (int j = 0; j < 3; j++) {
			int next_x = now.x + nextdir[j].first;
			int next_y = now.y + nextdir[j].second;
			if (0 <= next_x && next_x < n && 0 <= next_y && next_y < m) {
				if (!visited[next_x][next_y]) {
					visited[next_x][next_y] = true;
					q.push({ next_x, next_y, now.dist + 1 });
				}
			}
		}
	}
	return ret;
}

 궁수 한명이 표적을 찾는 함수입니다.  가장 짧은 거리의 적을 표적으로 삼는 조건이 있기 때문에 DFS보다 BFS가 적합하다고 판단하였습니다. 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int map[15][15];
int tmp[15][15];
int n, m, d;
int ans = 0;

typedef struct coord {
	int x;
	int y;
	int dist;
};

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

pair<int, int> decideTarget(int archer) {
	
	bool visited[15][15] = { false };
	pair<int, int> nextdir[3] = { {-1,0}, {0,1}, {0,-1} };
	pair<int, int> ret = { 999, 999 };
	queue<coord> q;
	int dist = 999;

	q.push({ n - 1, archer, 1 });

	while (!q.empty()) {

		coord now = q.front();
		q.pop();

		if ((dist != 999 && dist < now.dist) || now.dist > d) //이미 표적을 잡았는데 더 멀리 갈때, 공격 범위를 벗어 낫을 때
			break;

		if (tmp[now.x][now.y] == 1) {
			if (dist >= now.dist) {
				dist = now.dist;
				if(ret.second > now.y) //기존 표적보다 더 왼쪽에 있을 때
					ret = { now.x, now.y };
			}
		}

		for (int j = 0; j < 3; j++) {
			int next_x = now.x + nextdir[j].first;
			int next_y = now.y + nextdir[j].second;
			if (0 <= next_x && next_x < n && 0 <= next_y && next_y < m) {
				if (!visited[next_x][next_y]) {
					visited[next_x][next_y] = true;
					q.push({ next_x, next_y, now.dist + 1 });
				}
			}
		}
	}
	return ret;
}

int thisTurn(vector<int> &archers) {

	int cnt = 0;

	vector <pair<int, int>> targets;
	for (int i = 0; i < archers.size(); i++) {
		pair<int, int> target = decideTarget(archers[i]);
		if (target.first != 999 && target.second != 999) {
			targets.push_back(target);
		}
	}
	for (int i = 0; i < targets.size(); i++) {
		pair<int, int> target = targets[i];
		if (tmp[target.first][target.second] == 1) {
			tmp[target.first][target.second] = 0;
			cnt++;
		}
	}

	for (int i = n - 2; i >= 0; i--)
		for (int j = 0; j < m; j++) 
			tmp[i + 1][j] = tmp[i][j];
	for (int j = 0; j < m; j++)
		tmp[0][j] = 0;

	return cnt;
}

void comb(int cnt, int start, vector<int> &archers) {
	if (cnt == 3) {
		int result = 0;
		copyTmp();
		for (int i = 0; i < n; i++) {
			result += thisTurn(archers);
		}
		ans = max(ans, result);
		return;
	}
	for (int i = start + 1; i < m; i++) { //m이 가로 길이
		archers.push_back(i);
		comb(cnt + 1, i, archers);
		archers.pop_back();
	}
}

void solve() {
	vector<int> archers;
	comb(0, -1, archers);
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> d;

	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			cin >> map[i][j];
		
	solve();
	cout << ans;
}

개발 환경 : VS2019

질문, 지적 환영합니다!