[Algorithm]Baekjoon 17135번 : 캐슬 디펜스

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

17135번: 캐슬 디펜스

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
 
using namespace std;
 
struct Node
{
    int y;
    int x;
    int count;
};
 
int n, m, d;
int arr[15][15];
int tempArr[15][15];
bool visited[15][15] = { false };
int dirs[3][2] = { {0,-1}, {-1,0}, {0,1} };
int answer = 0;
vector<int> combination;
 
void BFS(int startY, int startX, int turn, vector<Node>& candidates) 
{
    memset(visited, false, sizeof(visited));
    queue<Node> q;
    int maxDistance = d - 1;
    visited[startY][startX] = true;
    bool isBreak = false;
 
    if (tempArr[startY][startX] == 1) candidates.push_back({ startY,startX,0 });
    q.push({ startY,startX,0 });
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curCount = q.front().count;
        q.pop();
 
        for (int i = 0; i < 3; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
            int nextCount = curCount + 1;
 
            if (nextY < 0 || nextY == n) continue;
            if (nextX < 0 || nextX == m) continue;
            if (visited[nextY][nextX]) continue;
            if (nextCount > maxDistance) continue;
 
            if (tempArr[nextY][nextX] == 1)
            {
                candidates.push_back({ nextY,nextX,nextCount });
                isBreak = true;
                break;
            }
 
            visited[nextY][nextX] = true;
            q.push({ nextY,nextX,nextCount });
        }
        if (isBreak) break;
    }
}
 
 
void DFS(int num)
{
    if (combination.size() == 3)
    {
        memcpy(tempArr, arr, sizeof(arr));
        int answerCount = 0;
 
        for (int i = 1; i <= n; ++i)
        {
            vector<Node> candidates[3];
 
            for (int j = 0; j < combination.size(); ++j)
            {
                int col = combination[j];
                BFS(n - i, col, i, candidates[j]);
            }
 
            for (int j = 0; j < 3; ++j)
            {
                if (candidates[j].size() > 0)
                {
                    if (tempArr[candidates[j][0].y][candidates[j][0].x] == 1)
                    {
                        ++answerCount;
                        tempArr[candidates[j][0].y][candidates[j][0].x] = 0;
                    }
                }
            }
        }
 
        answer = max(answer, answerCount);
        return;
    }
 
    for (int i = num + 1; i < m; ++i)
    {
        combination.push_back(i);
        DFS(i);
        combination.pop_back();
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> d;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    DFS(-1);
 
    cout << answer;
}
 

 

틀린부분 찾느라 사실상 하루종일 끙끙앓은 문제.

일단 궁수위치는 완탐으로 뽑으면 된다. 순서없이 뽑으면 되니 mC3인데, m값은 최대 15밖에 안되서 완전탐색으로 충분히 가능하다.

매 턴마다의 몬스터이동은 실제 몬스터를 아래로 내리기보다는 궁수위치를 한칸씩 올리는 방식으로 표현하면 된다.

 

일단 인지해야할 점은, '같은 적'을 공격할 수도 있다는 것이다. 절대적으로 인지해야한다.

그래서 실제공격처리하는부분을 나중에 처리해야한다. 본인이 생각할때 이번턴에 3명을 죽일 수 있는것 같은데, 실제로는 2명인 경우가 있다. 타겟을 선정하는 우선순위를 반드시 잘 구현해야한다.

 

그래서 위의 부분을 해결 후, 다시 제출했는데도 79%에서 자꾸 틀렸다고 떴다. 여기서 한참 헤매다가 공격후보군을 찾는 BFS를 수행할 때, 상하좌우를 탐색하게되는데 여기서 '하'를 탐색해서 문제였다.. 

궁수위치보다 아래쪽은 탐색하면 안됐는데... 그래서 상,좌,우만 탐색하게만 했더니 바로 통과했다.

 

그리고 여러 풀이들을 보면 일단 후보군들을 다 뽑은 후, 정렬시켜서 첫번째껄 기준으로 공격을 진행하는데 사실 그렇게 할 필요가 없다. 애초에 탐색자체를 좌,상,우 순서로 진행하다가 만나는 첫번째 몬스터가 무조건 최우선순위 공격대상이 된다.

칸이동의 가중치는 1이기 때문에 탐색방향에 따라 처음 만나는 몬스터가 해당 방향에서 처음으로 만나는 몬스터라는게 보장이 된다.

물론 N,M값이 작아서 턴마다 3번씩 정렬시켜도 시간초과가 되진 않지만, 앞으로 접할 문제가 N,M값이 항상 작으리란 보장은 없으니까 알아두는게 좋다.

 

실제로 각 턴마다 3번 정렬을 수행할 경우 48ms가 나왔는데, 정렬을 안하는 코드로 하면 4ms가 나온다.

N,M값이 크다면 아예 정렬하는 코드는 시간초과가 나올것이다.