JUST WRITE IT. HomeArchivesTagsCategories
백준 17135번 캐슬 디펜스
|AlgorithmBOJ|

#17135. 캐슬 디펜스

Problem

Solution

  1. 궁수 3명의 위치를 지정한다. (중복x, 오름차순 순열조합)
  2. 적이 사라질 때까지(=궁수가 0번째 행으로 이동할 때까지) 게임을 진행한다.
    1. 궁수는 가장 가까운 위치의 적을 공격해야 하며, 여럿이면 왼쪽의 적부터 공격한다. 또한 동시에 공격이 가능하다(=위의 조건을 만족하는 같은 적을 공격한다.)
    2. 공격이 끝나면 배열을 바꾸지 않고 궁수의 위치를 이동시킨다. (위로)
      step 변수를 두어 범위를 좁혀간다.

가까운 적을 먼저 찾아 공격하기 위해 BFS 탐색을 사용한다.

  • 각 궁수별로 queue 를 만들어 자신의 위치를 저장하고 탐색 시작 (최대 D까지)
  • 궁수가 적을 공격할 경우 다음 궁수에게 차례를 넘긴다. (즉, 공격하면 자신의 턴 끝=탐색 끝)
  • check array를 사용해 공격한 적일 경우 해당 step + 1의 값을 준다. (step이 0부터 시작, check는 0으로 초기화 되어있기에)
  • step을 이용해 check에 값을 준 이유는 다음 step에서 궁수의 위치가 이동될 때 이전 턴에서 공격 당해 제외된 적인지 아닌지를 판단하기 위함이다. (step의 값이 변하니까 중복되지 않게 탐색 가능)

1 Try

  • 궁수는 가장 가까운 위치의 적을 공격, 가까운 적이 여럿이면 왼쪽 우선 그리고 동시에 공격 가능하다는 조건을 충족하지 못 했다. → BFS를 이용하기로 결정
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    #include <iostream>
    #include <cstring>
    #include <cmath>
    using namespace std;
    int N, M, D, ans;
    int map[16][16];
    bool check[16][16];
    int archer[3] = { -1, -1, -1 };
    int getDistance(int a_x, int a_y, int b_x, int b_y) {
    	return abs(a_x - b_x) + abs(a_y - b_y);
    }
    void Game() {
    	int step = 0, res = 0;
    	memset(check, 0, sizeof(check));
    	while (true) { 
    		int attack_cnt = 0;
    		for (int i = N - step - 1; i >= (N -step) - D && i >= 0; --i) {
    			for (int k = attack_cnt; k < 3; ++k) { // 3명의 궁수
    				for (int j = 0; j < M; ++j) {
    					if (D >= getDistance(i, j, N - step, archer[k])
    						&& map[i][j] == 1 && !check[i][j]) { // 공격 개시
    						res++;
    						check[i][j] = true;
    						attack_cnt++;
    						break; // 한 번만 공격 가능
    					}
    				}
    			}
    		}
    		step++;
    		if (N - step - 1 < 0) break;
    	}
    	if (ans < res) ans = res;
    }
    void SelectPosition(int n, int cnt) {
    	if (cnt == 3) {
    		Game();
    		return;
    	}
    	for (int i = n; i < M; ++i) {
    		if (archer[cnt] != -1) continue;
    		archer[cnt] = i;
    		SelectPosition(i + 1, cnt + 1);
    		archer[cnt] = -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];
    		}
    	}
    	SelectPosition(0, 0);
    	cout << ans << "\n";
    	return 0;
    }

    2 Try

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    #include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    int N, M, D, ans;
    int map[16][16];
    int check[16][16];
    int archer[3] = { -1, -1, -1 };
    int dx[3] = { 0, -1, 0 };
    int dy[3] = { -1, 0, 1 };
    void Game() {
    	int step = 0, res = 0; // step은 1턴이 끝날 때 이동을 위함
    	memset(check, 0, sizeof(check));	
    	while (true) {
    		for (int i = 0; i < 3; ++i) { // 궁수 각 3명에 대하여
    			queue<pair<int, int> > q;
    			q.push({ N - step, archer[i] }); // 궁수 현재 위치부터 시작
    			for(int j = 0; j < D; ++j) { // 최대 D까지만큼만 탐색
    				int len = q.size();
    				bool end_flag = false; // 적을 공격했을 때 종료 flag
    				for (int k = 0; k < len; ++k) {
    					int x = q.front().first;
    					int y = q.front().second;
    					q.pop();
    					for (int dir = 0; dir < 3; ++dir) { // 왼 위 오 순서로 탐색 시작
    						int d_x = x + dx[dir];
    						int d_y = y + dy[dir];
    						if (d_x > -1 && d_y > -1 && d_x < N - step && d_y < M) { // N - step은 궁수 위치
    							if (d_x < N - step - D) continue; // [N - step - D, N-step) 탐색 범위
    							if (map[d_x][d_y] == 1 && check[d_x][d_y] == 0) { // 처음 적을 공격한 경우
    								res++;
    								check[d_x][d_y] = step + 1; // step을 옮겼을 때 중복 방지를 위함
    								end_flag = true;
    								break;
    							}
    							else if (map[d_x][d_y] == 1 && check[d_x][d_y] == step + 1) { // 동시에 적을 공격한 경우
    								end_flag = true;
    								break;
    							}
    							else { // 적을 발견하지 못 한 경우
    								q.push({ d_x, d_y });
    							}
    						}
    					}
    					if (end_flag) break;
    				}
    				if (end_flag) break;
    			}
    		}
    		step++;
    		if (N - step - 1 < 0) break; 
    	}
    	if (ans < res) ans = res;
    }
    void SelectPosition(int n, int cnt) {
    	if (cnt == 3) {
    		Game();
    		return;
    	}
    	for (int i = n; i < M; ++i) {
    		if (archer[cnt] != -1) continue;
    		archer[cnt] = i;
    		SelectPosition(i + 1, cnt + 1);
    		archer[cnt] = -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];
    		}
    	}
    	SelectPosition(0, 0);
    	cout << ans << "\n";
    	return 0;
    }
Algorithm