[백준] 17135 캐슬 디펜스

 

구현하는 문제다

문제 이해를 잘못해서 한시간넘게 틀리고 난리를 쳤다

문제를 자세히 보면 거리가 d이하인 적 중에 가깝고 가장 왼쪽에있는 적이 우선순위가 높다

아마 틀리는 사람들 대부분이 이 조건을 제대로 이해 못해서 틀리겠지...!

 

함수별로 기능을 살펴보자

 

inner()

 => 간단하게 범위를 넘어가는지 파악하는 함수

 

dist()

 => (x,y) , (a,b) 의 거리를 구해주는 함수

 

attack()

 => 공격할 적을 고르는 함수다 가장 헷갈리는 부분이였다

      내가 공격할 적을 거리기준,행기준,열기준으로 for문을 잡았다

      거리가 가까운 적들 중 왼쪽행에있는 적들을 봐준다

      만약 조건을 만족하는 적을 찾으면 vt에 넣고 끝!

 

solve()

 => 궁수 3명을 두고 적들을 총 몇명 죽이는지 계산해주는 함수다

      적들이 내려오는거나 궁수가 올라가는거나 같기 때문에 나는 궁수를 한칸 씩 올렸다

      현재 지점에서 적3명을 제거하고 한칸 씩 올라가고 함수가 끝나면 제거한 적을 복구시킨다

 

pick()

 => 궁수 3명의 위치를 잡아준다 n번째 칸에 궁수를 넣어주고 3명이 되면 sovle함수를 실행한다

 

input()

 => 입력받기!

 

구현실력이 떨어진다는걸 또다시 느낀다~~!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int n,m,d,ans;
int map[20][20];
int archer[3];
 
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<m);
}
int dist(int x,int y,int a,int b){
    return abs(x-a)+abs(y-b);
}
 
void attack(int x,int y,vector<pair<int,int>>&vt){
    for(int i=1;i<=d;i++){
        for(int j=0;j<m;j++){
            for(int k=x-1;k>=x-d;k--){
                if(inner(k,j) && map[k][j] && dist(x,y,k,j)==i){
                    vt.push_back({k,j}); return;
                }
            }
        }
    }
}
 
void solve(int pos,int kill){
    if(pos==0) {
        ans = max(ans,kill); return;
    }
 
    int cnt=0;
    vector<pair<int,int>> vt;
    for(int i=0;i<3;i++) attack(pos,archer[i],vt);
    for(int i=0;i<vt.size();i++) {
        if(map[vt[i].first][vt[i].second]==1){
            map[vt[i].first][vt[i].second]=0;
            cnt+=1;
        }
    }
    solve(pos-1,kill+cnt);
    for(int i=0;i<vt.size();i++) map[vt[i].first][vt[i].second]=1;
}
 
void pick(int cnt,int now){
    if(cnt==3) {
        solve(n,0); 
        return;
    }
    for(int i=now;i<m;i++){
        if(map[n][i]) continue;
        map[n][i]=1;
        archer[cnt] = i;
        pick(cnt+1,i);
        map[n][i]=0;
    }
}
 
void input(){
    scanf(" %d %d %d",&n,&m,&d);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %d",&map[i][j]);
        }
    }
}
 
int main(){
    freopen("input.txt","r",stdin);
    input();
    pick(0,0);
    printf("%d\n",ans);
}

 

소스코드 (Java)

package asdasdas;
 
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
public class Main {
    public static int n,m,d,ans;
    public static int[][] map,originalMap;
    public static int[] archer;
    
    public static void copy() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                map[i][j]=originalMap[i][j];
            }
        }
    }
    public static void input() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        d = sc.nextInt();
        map = new int[n+1][m+1];
        originalMap = new int[n+1][m+1];
        archer = new int[3];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                map[i][j]=sc.nextInt();
                originalMap[i][j]=map[i][j];
            }
        }
    }
    public static int solve() {
        int killed=0;
        for(int i=n;i>=1;i--) killed+=findEnemy(i);
        copy();
        return killed;
    }
    public static void pick(int pos,int cnt) {
        if(cnt==3) {
            ans = Math.max(ans, solve()); return;
        }
        for(int i=pos;i<m;i++) {
            archer[cnt]=i;
            pick(pos+1,cnt+1);
        }
    }
    public static int enemy(int ax,int ay) {
        for(int i=1;i<=d;i++) {
            for(int y=0;y<m;y++) {
                for(int x=ax-1;x>=0;x--) {
                    if(map[x][y]==1 && dist(ax,ay,x,y)==i) return (x*m+y);
                }
            }
        }
        return -1;
    }
    public static int findEnemy(int pos) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i=0;i<3;i++) set.add(enemy(pos,archer[i]));
        while(set.remove(-1));
        for(int e:set) {
            int x = e/m;
            int y = e%m;
            map[x][y]=0;
        }
        return set.size();
    }
    public static int dist(int x1,int y1,int x2,int y2) {
        return (Math.abs(x1-x2) + Math.abs(y1-y2));
    }
    public static void main(String[] args) {
        input();
        pick(0,0);
        System.out.println(ans);
    }
}