백준 17135 캐슬 디펜스

캐슬 디펜스

이번 문제는 아기상어 문제를 풀고 조금더 어려운 문제를 풀어보고 싶어서 도전한 문제다.
날 너무 힘들게 했다. 너무 어려웠다..

문제분석

첫째, 0~n-1행까지는 맵이 나오고, n번째 행에는 궁수가 존재할수도, 존재하지 않을 수도 있다. 그중에 3곳에 궁수가 존재한다.

dfs, 브루트포스(재귀) 어떤걸로 구현해도 상관 없다. 성의 위치 중 3가지를 고르기만 하면 된다.
다만 브루트포스에서 주의할 점은, 1 2 3과 1 3 2는 같은경우이므로 중복제거를 꼭 해주어야한다.

둘째, 각 궁수가 위치하고 있는 자리에서 가장 가까운 적(여러 위치가 있다면, 가장 왼쪽)을 공격한다. 공격당한 적은 제외된다.

이 부분이 이 문제에서 가장 까다로운 부분이다. 각 궁수의 위치에서 최단거리 적을 발견했을 때 바로 제외하지 않고 한 라운드가 끝나고나서 모든 궁수가 적을 쏜 후에 적을 제외시켜줘야한다

셋째, 궁수가 쏠 수 있는 거리는 d로 한정되어있다

bfs탐색에서 d보다 dist가 클 때 continue하면 된다.

넷째, 한 라운드가 끝나면 모든 적이 한칸씩 내려온다.

이부분은 궁수가 한칸 올라간다고 처리해주면 굳이 모든 적을 밑칸으로 옮길 필요 없다.

문제풀이 후 든 생각

아직 실력이 너무 부족하다. 궁수를 세 곳에 위치시키고 bfs로 최단거리 탐색까지는 잘 생각해냈고 문제도 술술 풀린거 같았지만, 같은 적이 여러 궁수에게 공격당할 수 있다 조건 때문에 거의 이틀이나 고민했다. 당연히 최대값이니까 적이 공격당하면 바로 제외시킨 게 결정적인 패인이 되었다.

5 5 2
1 0 1 1 1
0 1 1 1 1
1 0 1 0 1
1 1 0 1 0
1 0 1 0 1
경우엔 내 코드에서는 15를 구했고, 정답은 14이다.
더 적을 경우가 존재하는 것이다.
사실 이 조건을 제외하고도, 내 논리를 코드로 구현하는게 많이 부족하다는 것을 깨달았다.
연습을 많이 해야겠다.

소스

#include<iostream>
#include<bits/stdc++.h>

using namespace std;
int ma[20][20];
int x_index[4]={-1,0,0};
int y_index[4]={0,-1,1};
int n,m,d;
bool where[20]={0};

tuple<int,int,int> bfs(int ar_x,int ar_y){
    queue<pair<int,int>> q;
    q.push(make_pair(ar_x,ar_y));
    vector<tuple<int,int,int>> ans;
    int dist[20][20]={0};
    int cnt=0;
    int visited[20][20]={0};
    visited[ar_x][ar_y]=1;
    while(!q.empty()){
        int nx,ny;
        tie(ar_x,ar_y)=q.front(); q.pop();
        visited[ar_x][ar_y]=true;
        if(cnt==0)
        {
            nx=ar_x+x_index[0];
            ny=ar_y+y_index[0];
            if(nx>=0&&nx<n&& ny>=0 && ny<m){
                dist[nx][ny]=1;
                if(ma[nx][ny]==1)
                {
                    ans.push_back(make_tuple(dist[nx][ny],ny,nx));
                }
                
                q.push(make_pair(nx,ny));
            }
            cnt++;
        }
        else{
            for(int i=0;i<3;i++)
            {
                nx=ar_x+x_index[i];
                ny=ar_y+y_index[i];
                if(nx>=0&&nx<n&& ny>=0 && ny<m){
                    dist[nx][ny]=dist[ar_x][ar_y]+1;
                    if(dist[nx][ny]>d || visited[nx][ny]==1)
                        continue;
                    if(ma[nx][ny]==1)
                    {
                        ans.push_back(make_tuple(dist[nx][ny],ny,nx));
                    }
                    q.push(make_pair(nx,ny));
                }
            }
        }
    }
    if(ans.empty())
    {
        
        return make_tuple(-1,-1,-1);
    }
    sort(ans.begin(),ans.end());
    return ans[0];
    
}


int cal(){
    int ar_x;
    int x,y,z;
    int ans=0;
    
    for(int i=n-1;i>=0;i--){// 행의 개수만큼 실행
        ar_x=i+1;
        vector<pair<int,int>> enemy;
        for(int j=0;j<m;j++){
            if(where[j]==true)
            {
                tie(z,y,x)=bfs(ar_x,j);
                if(z==-1)
                    continue;
                enemy.push_back(make_pair(x,y));
            }
        }
        int e_x,e_y;
        sort(enemy.begin(), enemy.end());
        enemy.erase(unique(enemy.begin(),enemy.end()),enemy.end());
        for(auto ene : enemy){
            e_x=ene.first;
            e_y=ene.second;
            ma[e_x][e_y]=3;
            ans++;
        }
        
    }
    for(int i=0;i<n;i++){// 행의 개수만큼 실행
        for(int j=0;j<m;j++){
        if(ma[i][j]==2||ma[i][j]==3)
            ma[i][j]=1;
        }
    }
    
    return ans;
}

int go(int index, int person){ //궁수 명수
    int ans=0;
    if(person==3)
    {
        ans=cal();
        return ans;
    }
    
    for(int i=index;i<m;i++)//열의개수만큼 3가지 경우 고름
    {
        if(where[i]==true)
        {
            continue;
        }
        where[i]=true;
        ans=max(ans,go(i+1,person+1));
        where[i]=false;
    }

    return ans;
}

int main(){
    cin>>n>>m>>d;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cin>>ma[i][j];
    }
    cout<<go(0, 0)<<'\n';
    

}