[백준/C++] 17138번 캐슬 디펜스 풀이

---

최대 N과 M이 15이고 궁수는 3명이니 브루트포스로 실행할 경우 최대 ₂₂₅C₃이다. 이는 대략 180만번이고

각각에 궁수가 15턴을 실행할 경우를 계산하면 180만 * 15 * 3으로 8천만번이고 1억번 이내이므로 브루트포스로 풀어낼 수 있는 문제이다.

 

먼저 궁수 3명의 위치를 선정하기 위해 SetArcher 함수로 모두 구해주었다.이후 Simulate 함수를 통해 15턴동안 어떤 궁수가 어디 위치한 적을 쐈는지를 체크하고 죽인 적은 제거해주었다.이 때 매 턴이 지나가는 것을 15x15 게임맵을 아래로 한칸씩 내리고 위에 0으로만 이뤄진 배열을 추가해주었다.

 

매 턴마다 PlayOnTurn 함수를 실행시켰으며 이 함수에서 BFS로 가장 가까이 있으면서 가장 왼쪽에 있는 적을 우선적으로 찾아주었다. 만약 궁수의 사거리를 벗어나거나 쏠 적을 찾지 못했다면 (-1,-1)을 리턴해 아무도 쏘지 않았다는 것을 체크했다.

---

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

//class for location
class Human
{
public:
    int x_ ;
    int y_ ;
    Human() {x_ = 0, y_ = 0 ;}
    Human(int x, int y) {x_ = x, y_ = y;}
};

int N, M, D, max_answer ;
int _map[15][15] ;
bool visited[15] ;
Human archer[3] ;

//BFS로 한 턴을 실행.
Human PlayOneTurn(int idx, int new_map[15][15])
{
    int dist = 1 ;
    bool check[15][15] ;
    memset(check, 0, sizeof(check)) ;
    
    //BFS를 할 때 왼쪽 이후 위 왼쪽, 이후 오른쪽을 찾도록 순서 배정
    int x_dist[] = {0, -1, 0, 1} ;
    int y_dist[] = {-1, 0, 1, 0} ;
    
    queue<Human> que ;
    que.push(archer[idx]) ;

    while(!que.empty())
    {
        int q_sz = que.size() ;
        for(int j = 0 ; j < q_sz ; j++)
        {
            Human front = que.front() ; que.pop() ;
            for(int i = 0 ; i < 4 ; i++)
            {
                int x_new = front.x_ + x_dist[i] ;
                int y_new = front.y_ + y_dist[i] ;

                if(x_new >= N || y_new >= M || x_new < 0 || y_new < 0) continue ;
                if(dist > D) return Human(-1, -1) ;
                if(new_map[x_new][y_new]) return Human(x_new, y_new) ;

                if(!check[x_new][y_new])
                {
                    check[x_new][y_new] = 1 ;
                    que.push(Human(x_new, y_new)) ;
                }
            }
        }
        dist++ ;  
    }

    return Human(-1, -1) ;
}

//시뮬레이션으로 적 처지 횟수 카운트
void Simulate()
{
    int round = 0, answer = 0 ;
    int new_map[15][15] ;
    Human dead[3] ;
    memcpy(new_map, _map, sizeof(_map)) ;
    while(round <= 15)
    {
        for(int i = 0 ; i < 3 ; i++)
            dead[i] = PlayOneTurn(i, new_map) ;

        for(int i = 0 ; i < 3 ; i++)
        {
            if(dead[i].x_ != -1 && dead[i].y_ != -1 && new_map[dead[i].x_][dead[i].y_] == 1)
            {
                answer++ ;
                new_map[dead[i].x_][dead[i].y_] = 0 ;
            }
        }

		//게임 맵을 한칸씩 내리고 맨위에 공백 배열을 채워줌
        for(int i = N - 2 ; i >= 0 ; i--)
            memcpy(new_map[i + 1], new_map[i], sizeof(new_map[i])) ;
        memset(new_map[0], 0, sizeof(new_map[0])) ;
        
        round++ ;
    }

    max_answer = max(answer, max_answer) ;
}

//궁수 사용하는 조합 찾기.
void SetArcher(int idx, int depth)
{
	for (int i = 0 ; i < M; i++)
		for (int j = i + 1 ; j < M; j++)
			for (int k = j + 1 ; k < M; k++)
			{
                archer[0] = Human(N, i) ;
                archer[1] = Human(N, j) ;
                archer[2] = Human(N, k) ;
                Simulate() ;
            }
}

int main()
{
    ios::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] ;
    
    SetArcher(0, 0) ;

    cout << max_answer ;
}

---

느낀점: 아직 구현문제를 30분 이내에 쳐내지 못하는데 좀 더 코드를 간결하고 정확하게 짜도록 연습해야겠다.

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

17135번: 캐슬 디펜스