백준 17135번 캐슬 디펜스 C++ 브루트포스, DFS, BFS, 구현, 시뮬레이션

리뷰

 

쉽게 접근했다가 꽤나 애먹은 문제, 딱히 엣지케이스가 있는 것 같지는 않은데 써야할 알고리즘이 많고, 생각해 주어야 할 부분이 많아서 코드가 길어지기에 실수가 잘 나올 것 같다.

 

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

 

 

문제 풀이

1. input 함수를 통해 n, m, d 값을 받고 정답을 출력한 ans를 0으로, 이후 맵을 초기화 해 주었다.
2. 궁수 좌표 및 이동 범위 정보를 담을 구조체 Pos를 만들고 해당 벡터 col을 만들어 dfs를 실행해 주었다.
3. dfs 함수의 매개변수로는 level과 궁수 3명의 정보를 담을 Pos 타입 벡터 col이다.
4. 궁수 세명을 담을 것인데, 중복을 허용하지 않는 순서가 있는 조합으로 궁수를 벡터 col에 담아준다.
5. 123, 124, 125 ... 356, 456 같이 중복이 없는 주사위를 생각하면 된다.
6. 궁수를 담을 때마다 level을 올려 재귀를 실행하고, 궁수 세명이 모이면 bfs를 시작한다.
7. 궁수 정보가 담긴 벡터 col을 bfs의 매개변수로 전달해 주고, 맵 정보를 하나 복사해 준다.
8. 적군은 턴마다 성을 향해 전진하므로 행의 갯수 n만큼의 반복문으로 시뮬레이션을 돌려준다.
9. 매 턴마다 각 궁수를 simulation을 돌려준다. simulation의 매개변수로는 궁수, 맵, 적을 잡은 정보 벡터이다.
10. 궁수의 사정거리 내에서 잡을 수 있는 적(맵에서 1인 경우)을 탐색한 뒤 타겟이 있다면 저장하고 리턴해 준다.
11. 문제에 같은 적이 여러 궁수에게 공격당할 수 있다.는 조건이 있기에 잡은 적을 체크하고, 동일한 적이 아닐 경우에만 적을 잡은 숫자를 기록해 준다.
12. 모든 시뮬레이션을 진행하고 적을 잡은 총 숫자를 리턴해 준다.
13. ans에 저장된 값과 비교하여 최대값을 계속 갱신해 나가며 dfs 재귀를 돌아주면 된다.
14. 모든 재귀, 시뮬레이션이 끝난 경우 ans를 출력해 준다.

 

참고 사항

1. 하나의 칸에는 최대 1명의 궁수만 있을 수 있다.
2. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다.
3. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이다.
4. 가장 가까운 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.
5. 같은 적이 여러 궁수에게 공격당할 수 있다.
6. 궁수의 공격이 끝나면, 적이 이동한다.

 

정답 코드

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

using namespace std;

int n, m, d, ans;
vector<vector<int>> lst;
int v[15] = { 0, }; 

int dx[] = { 0, -1, 0}; // 3방향 체크, 왼쪽 먼저
int dy[] = { -1, 0, 1};

struct Pos {
	int x, y, move;
};

void input() { // 초기화 관련 함수
	cin >> n >> m >> d;
	lst.resize(n, vector<int>(m, 0));
	ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lst[i][j];
		}
	}
}

void simulation(Pos archer, vector<vector<int>>& map, vector<Pos>& targets) { // 궁수 하나의 시뮬레이션 함수
	int visit[15][15] = { 0, };
	queue<Pos> simul;
	simul.push(archer);
	while (!simul.empty()) { // 가장 가까운 적 찾기
		Pos pos = simul.front(); simul.pop();
		int cx = pos.x, cy = pos.y, cm = pos.move;
		for (int i = 0; i < 3; i++) {
			int nx = cx + dx[i], ny = cy + dy[i], nm = cm + 1;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !visit[nx][ny]) {
				visit[nx][ny] = 1;
				if (map[nx][ny] == 1) {
					targets.push_back({ nx, ny });
					return;
				}
				if (nm == d) continue; // 사정거리를 벗어나면 continue
				simul.push({ nx, ny, nm });
			}
		}
	}
}

void print(vector<vector<int>>& map) { // 디버깅용 함수
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}

int bfs(vector<Pos> col) { // 궁수 세명이 얼마나 많은 적을 잡는지 체크
	vector<vector<int>> map = lst;
	int distroy = 0;
	for (int i = 0; i < n; i++) { // 행의 수만큼 시뮬레이션이 필요
		vector<Pos> Archer = col;
		vector<Pos> targets; // 잡은 적을 저장할 벡터
		for (int j = 0; j < 3; j++) { // 궁수 세명이 각자 시뮬레이션을 돌린다.
			Pos archer = Archer[j];
			simulation(archer, map, targets);
		}
		for (Pos pos : targets) { // 잡은 적을 맵에서 0으로 만들어 준다.
			if (map[pos.x][pos.y]) {
				map[pos.x][pos.y] = 0;
				distroy++;
			}
		}
		//print(map);
		for (int k = 0; k < m; k++) map[n - 1][k] = 0; // 가장 아랫줄 모두 0으로
		for (int j = n - 1; j > 0; j--) { // 맵을 한칸씩 아래로 내린다.
			for (int k = 0; k < m; k++) {
				int temp = map[j][k];
				map[j][k] = map[j - 1][k];
				map[j - 1][k] = temp;
			}
		}
	}
	return distroy;
}

void dfs(int level, vector<Pos> col) { // 중복 불가능, 순서가 있는 조합
	if (level == 3) { // 기저 조건
		ans = max(ans, bfs(col)); // 궁수 세명의 위치가 확보 되면 bfs 실행
		return;
	}
	for (int i = 0; i < m; i++) { // 열의 개수만큼 반복문 실행
		if (v[i]) continue;
		if (!col.empty() && col[level - 1].y > i) continue;
		v[i] = 1;
		col.push_back({n, i, 0});
		dfs(level + 1, col);
		col.pop_back();
		v[i] = 0;
	}
}

int main() {
	input();
	vector<Pos> col;
	dfs(0, col);
	cout << ans;
}