백준 17135번 - 캐슬 디펜스

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

문제를 풀기 위해서는 DFS나 BFS를 활용해야 하지만,

전반적으로 구현을 하는 부분이 더 많은 비중을 차지하는 것 같아서 시뮬레이션에 문제를 담았다.

먼저 문제를 해결하기 위한 순서는 다음과 같다.

1. 3명의 궁수 자리 배치
2. 현재 궁수의 위치에서, 거리 1부터 D까지 잡을 수 있는 적 확인
3. 잡은 적의 수와 좌표 확인 후 업데이트 및 적의 위치 아래로 이동
4. 1~3번의 과정 마무리하면, 다시 3명의 궁수 자리 배치 변경 후 반복 실행

궁수의 자리 배치를 위해 dfs 함수로 배치를 시킨 후

3명이 배치가 완료되면 현재 궁수의 위치에서 잡을 수 있는 적들을 확인했다.

다른 분들의 풀이를 봤을 때, 우선선위 큐를 이용해서 해결한 것을 보았는데

나는 현재 궁수의 위치에서 1부터 D까지, 왼쪽에서 오른쪽 방향으로 적들을 확인할 수 있도록 했다.

현재 궁수 위치를 기준으로 위의 그림에서 공격할 수 있는 위치의 거리를 숫자로 나타내었다.

거리가 1일 때, 2일 때, 3일 때, 각각 왼쪽에서 오른쪽 방향으로 검사를 할 수 있도록 했다.

현재 궁수의 위치를 기준으로 각각의 거리에 따라 검사를 해야할 y,x 좌표는 

2중 for문으로 구현할 수 있도록 했다.

또한, 적을 발견했을 때 이전에 잡았던 적을 한 번 더 추가해주지 않도록 예외처리를 해주면 된다.

마지막으로 3번 과정에서 적을 아래로 이동시킨다고 나와있는데

모든 적들을 아래로 이동시키는게 번거롭다고 생각해서 현재 3명의 궁수 위치를 올려주는 방향으로 문제를 해결했다.

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
 
struct str{
    int y;
    int x;
    str(int y,int x): y(y),x(x){};
};
 
int N,M,D;
int ans=0;
vector<str> archor; //궁수 위치
vector<vector<int>> map; //격자판
 
void solve(){
    
    vector<vector<int>> tmp_map=map;
    vector<str> tmp_archor=archor;
    vector<vector<int>> visit(N+1,vector<int> (M,0)); //적 발견시 이전에 발견 유무
    
    int cnt=0;
    for(int i=0;i<N;i++){
        
        queue<pair<int,int>> q;
        for(int j=0;j<3;j++){
            
            bool check=false;
            for(int distance=1;distance<=D;distance++){
                
                int dy=-1;
                int dx=(distance-1)*(-1);
                
                for(int k=1;k<2*distance;k++){
                    
                    int ny=tmp_archor[j].y+dy;
                    int nx=tmp_archor[j].x+dx;
                    
                    //y,x좌표 갱신
                    dy=(k>=distance)? dy+1:dy-1;
                    dx+=1;
                    
                    if(ny<0 || nx<0 || nx>=M)
                        continue;
                    
                    //적 발견시
                    if(tmp_map[ny][nx]==1){
                        
                        //동시에 맞힌 적은 1명만 잡도록 하기 위해
                        if(visit[ny][nx]==0){
                            cnt++;
                            visit[ny][nx]=1;
                            q.push(make_pair(ny,nx));
 
                        }
                        
                        check=true;
                        break;
                    }
                    
                }
                if(check)
                    break;
            }
            
            tmp_archor[j].y--; // 궁수 y좌표 위로
        }
        
        //잡은 적 0으로 갱신
        while(!q.empty()){
            int ny=q.front().first;
            int nx=q.front().second;
            q.pop();
            
            tmp_map[ny][nx]=0;
        }
        
    }
    
    ans=max(ans,cnt);
}
 
void dfs(int location_x,int cnt){
    if(cnt==3){
        solve();
        return;
    }
    
    //나머지 모두 궁수 배치해도 3명 안되거나 범위 넘을때
    if(location_x>=M || cnt+(M-location_x)<3)
        return;
    
    archor.push_back(str(N,location_x));
    dfs(location_x+1,cnt+1);
    
    archor.pop_back();
    dfs(location_x+1,cnt);
}
 
int main() {
    
    cin>>N>>M>>D;
    
    map=vector<vector<int>> (N+1,vector<int> (M,0));
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin>>map[i][j];
    
    dfs(0,0);
    cout<<ans<<endl;
    return 0;
}