[백준][C++] 17135번: 캐슬 디펜스 <176>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

17135번: 캐슬 디펜스

생각의 흐름

구현 문제는 생각의 순서를 정하는것이 중요하다. 어떤 순서로 진행되어야 할까?

 

1. 3명의 궁수를 N+1 번지에 배치한다.

2. 원본 map을 복사한 copyMap 만들기(궁수 배치의 case 마다 한번씩 복사해주어야 한다)

3. 왼쪽 궁수부터 BFS 탐색을 진행하면서, 가장 가까운 적을 공격표시 한 후, 다음 궁수에게 넘긴다.

4. 3명의 궁수의 공격이 끝나면, check된 적의 배열값은 0으로 변경시켜 준다. copyMap[i][j] = 0

이때 3명의 궁수 모두 체크가 끝난후 0을 대입해주어야 한다. 같은 적을 공격할수도 있기 때문이다.

5. 궁수들을 한칸 전진시킨다(== 적들을 한칸 아래로 당긴다)

6. 하나의 case가 끝나면 결과값을 갱신한다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 17

int N, M, D;
int MAP[MAX][MAX];
int copyMap[MAX][MAX];
bool visited[MAX][MAX];
bool check[MAX][MAX];
int res = INT_MIN;

int dx[3] = {0, -1, 0}; // 좌, 상, 우 
int dy[3] = {-1, 0, 1};

void mapToCopy(){
	memset(check, false, sizeof(check));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			copyMap[i][j] = MAP[i][j];
		}
	}
}

void game(int a, int b, int c){
	mapToCopy();
	int archer[3] = {a, b, c};
	int pos = N;
	int kill = 0;
	
	while(pos > 0){
		for(int i = 0; i < 3; i++){
			memset(visited, false, sizeof(visited));
			int arX = pos;
			int arY = archer[i];
			
			queue<pair<int, int> > Q;
			Q.push({arX-1, arY});
			visited[arX-1][arY] = true;
			
			while(!Q.empty()){
				int nowX = Q.front().first;
				int nowY = Q.front().second;
				Q.pop();
				
				if(copyMap[nowX][nowY] == 1){ // 적이라면 check 해두기  
					check[nowX][nowY] = true;
					break;
				}
				for(int j = 0; j < 3; j++){
					int nx = nowX + dx[j];
					int ny = nowY + dy[j];
					
					if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
					
					if(!visited[nx][ny] && (abs(arX-nx) + abs(arY-ny) <= D)){
						visited[nx][ny] = true;
						Q.push({nx, ny});
					}
				}
			}
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(check[i][j]){
					copyMap[i][j] = 0;
				}
			}
		}
		pos--;
	}
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(check[i][j]){
				kill++;
			}
		}
	}
	
	res = max(res, kill);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	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 < M-2; i++){
		for(int j = i+1; j < M-1; j++){
			for(int k = j+1; k < M; k++){
				game(i, j, k);
			}
		}
	}
	
	cout << res;
	
	return 0;
}