백준 17135 (캐슬 디펜스) - java

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

17135번: 캐슬 디펜스

삼성 문제는 개인적으로 순차적인 정리가 중요하다. 이게 무슨 말이냐면 .... 과정에 있어 필요한 것들을 메소드로 정리해야지만 가독성 있게 문제를 해결할 수 있다.

주요 기능

1. 궁수 3명 : 백트랙킹을 이용한 조합론으로 3명의 궁수를 배치한다.
2. 공격 기준 : 거리가 가까운가 , 더 왼쪽에 있는가에 대한 우선순위 정리
3. 1턴 궁수의 공격이 끝난 후 : 모든 칸들이 한 칸 아래로 이동
   1. 궁수를 위로 한 칸 올릴 것인가 ?
   2. 좌표를 그냥 아래로 한칸 이동할 것인가 ? : 내가 선택한 기준 ( 정형화하기 더 편하다 판단 )

과정

1. 조합론을 통해 궁수 3명을 배치 (travel)
2. 3명이 배치된 경우 game() 실행 하여 제거된 적의 수를 갱신
3. game() 내에서는 궁수의 공격 , down()을 모든 적이 사라질 때 까지(check())로 실행

import java.io.*;
import java.util.*;

public class Main {
    static int[][] board = new int[16][16];
    static int[][] tmp = new int[16][16]; // 복사 배열
    static int[] arrow = new int[4]; // 궁수의 위치
    static int n = 0;
    static int m = 0;
    static int d = 0;
    static int result = 0;
    static Queue<point> dead = new LinkedList<>(); // 죽은 적들을 저장
    static int[] dx = {-1,0,0};
    static int[] dy = {0,-1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=m;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        travel(1,1);
        System.out.println(result);
        br.close();
    }
    
    // 각 경우 ( 궁수 3명 배치 ) 에 대해 좌표계를 복사하여 실행
    static void copy()
    {
        for(int i=1;i<=n;i++) {
            for (int j = 1; j <= m; j++) {
                tmp[i][j] = board[i][j];
            }
        }
    }
    
    // 1턴 궁수의 공격이 완료된 후 좌표계를 한 칸 아래로 이동
    static void down()
    {
        for(int i=n-1;i>=1;i--)
        {
            for(int j=1;j<=m;j++)
            {
                tmp[i+1][j] = tmp[i][j];
            }
        }

        for(int j=1;j<=m;j++)
            tmp[1][j] = 0;

    }
    // k : 궁수가 배치된 수(3명 배치) , cur : 다음에 배치될 궁수의 번호
    // 조합론 
    static void travel(int k,int cur)
    {
        if(k==4)
        {
            copy();
            int tmp = game();
            if(tmp>result)
               result = tmp;
            return;
        }

        for(int i=cur;i<=m;i++)
        {
            arrow[k] = i;
            travel(k+1,i+1);
            arrow[k] = 0;
        }
    }
    
    // 적이 모두 사라졌는지 판단하는 메소드
    static boolean check()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(tmp[i][j]==1)
                    return true;
            }
        }

        return false;
    }
    // 적이 모두 사라질 때까지 (궁수의 공격 , 한 칸 좌표 이동)을 반복
    static int game()
    {
        int result = 0;

        while(check()) {
            result = result + attack();
            down();
        }
        return result;
    }
    
    // 공격하는 함수
    static int attack()
    {
        int num = 0;
        
        // 각 궁수에 대하여
        for(int i=1;i<=3;i++)
        {
            // 바로 위의 좌표 (거리가 1)
            if(tmp[n][arrow[i]]==1)
            {
                dead.add(new point(n,arrow[i]));
            }
            
            // bfs 실행
            else{
                Queue<point> q = new LinkedList<>();
                boolean[][] visit = new boolean[16][16];
                q.add(new point(n,arrow[i]));
                visit[n][arrow[i]] = true;
                int tx = -1;
                int ty = -1;
                int td = -1;
                while(!q.isEmpty())
                {
                    point cur =q.poll();
                    for(int j=0;j<3;j++)
                    {
                        int nx = cur.x + dx[j];
                        int ny = cur.y + dy[j];
                        if(nx>=1&&nx<=n&&ny>=1&&ny<=m) {
                            if (!visit[nx][ny]){
                                visit[nx][ny] = true;
                                int dis = Math.abs(nx-(n+1)) + Math.abs(ny - arrow[i]);

                                if(dis<=d)
                                {
                                    if(tmp[nx][ny]==1) {
                                        // 우선순위 1 : 거리가 가까운 순
                                        if (td == -1 || td > dis) {
                                            td = dis;
                                            tx = nx;
                                            ty = ny;
                                        }
                                        // 우선순위 2 : 더 왼쪽에 있는가
                                        else if (td == dis && ty > ny) {
                                            td = dis;
                                            tx = nx;
                                            ty = ny;
                                        }
                                    }
                                    // 거리가 여유가 있는 경우 계속 탐색
                                    q.add(new point(nx,ny));
                                }
                            }
                        }
                    }
                }
                // 죽일 수 있는 적을 찾은 경우 추가
                if(tx!=-1&&ty!=-1)
                    dead.add(new point(tx,ty));
            }
        }

        
        // 적들을 공격 , 겹치는 경우에는 카운트가 1이어야 하므로 적절히 !
        while(!dead.isEmpty())
        {
            point body = dead.poll();
            if(tmp[body.x][body.y]==1)
            {
                tmp[body.x][body.y] = 0;
                num = num + 1;
            }
        }
        return num;
    }

}
class point
{
    int x;
    int y;

    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}