[JAVA] 백준 - 캐슬 디펜스 17135 (테케 다 맞는데 틀린다면?)

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

자꾸 틀린다면 꼭 점검해야할 상황을 소개한다. (본인 경험)

 

1. 궁수 3명을 배치하는 모든 경우를 구했는가?

- 문제에서 N+1 번째 칸에 궁수 3명을 배치한다고 하였다. 한 칸에 한명만 올 수 있다. 따라서 M개의 자리에서 3개를 선택하는 모든 경우의수를 구해야한다. Combination 로직을 DFS로 구현해주면 된다.

 

여기에서 M = 5 일때 3개의 자리를 선택하는 경우의 수는 5C3 이므로 10가지가 나와야한다. 0부터 4까지의 숫자중에 3가지를 선택하는 경우의 수는 다음과 같다.

 

(0,1,2)

(0,1,3)

(0,1,4)

(0,2,3)

(0,2,4)

(0,3,4)

(1,2,3)

(1,2,4)

(1,3,4)

(2,3,4)

 

위 처럼 모든 경우의 수를 적절하게 구하는지 점검해본다.

 

 

2. 궁수는 모두 동시에 공격하고 같은 적을 공격할 수 있다.

- 이 부분을 놓쳐서 자꾸 틀렸었다. 각각의 궁수별로 적을 찾은 다음에 적을 죽이는 것이 아니라 3명의 궁수의 타겟을 모두 구하고 타겟들을 제거하는 것이다. 발견하자마자 죽이는 것이 아니라 모두 적을 찾아 놓은 다음에 적을 죽여야 한다.

 

즉, 적은 2명 없어 졌는 데 죽인 적을 카운트는 3명이 될 수 있다는 소리다.

예를 들어 궁수 A,B,C 의 타겟이 D,D,E 인데 D는 1번 죽였지만 2번 카운트 될 수 있다. 

 

3. 왼쪽으로 갈수록 우선순위가 높다. 우선순위대로 잘 찾고 있는지 확인하라.

- 예를 들어 다음과 같은 배열이 있다고 가정하자.  N = 3 , d(사거리) = 3

 

0 1 0

1 0 1

0 0 0

 

궁수가 N+1 행의 중앙에 있다고 할때 

 

0 1 0

0 0 1

0 0 0

 

왼쪽의 적을 잡는지 확인해보자. 

 

4. Search  =  { 왼쪽 , 위 , 아래 , 오른쪽  } 순으로 우선순위를 정할 것. 여기서 아래가 빠진지 확인하라.

- 이 부분은 정확한 반례를 찾지 못했지만 아래가 빠지면 모든 경우의 수를 커버하지 못하는 듯 하다. 

 

 

5. 적들의 위치를 기록하는 배열이 유지 되는 것이 필요하다.

- 하나의 배열로 사용하면 초기 배열의 상태를 모르기 때문에 초기 배열의 상태는 그대로 유지해야한다. 배열을 아래로 이동시킬 때 배열을 복사한 복사본을 사용할 것.

 

6. 격자판의 좌표들 사이 거리는 문제가 제시하는 공식을 사용할 것.

- 그냥 이동한 칸수로 설정하면 좌표사이 거리와 달라질 가능성도 있기 때문이다.

 

7. 항상 적을 잡는 것이 아니다.

- 적을 잡지 않는 경우인데 처리하는 경우를 조심할 것.

 

 

<자바 코드>

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main{

    static int n,m,d;
    static int[][] arr;
    static ArrayList<int[]> loc = new ArrayList<>();
    static int[][] dir = new int[][]{
            {0,-1}, // left
            {-1,0}, // up
            {1,0}, // down
            {0,1} // right
    };

    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        n = sc.nextInt();
        m = sc.nextInt();
        d = sc.nextInt();
        arr = new int[n+1][m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j] = sc.nextInt();
            }
        }
        mC3(0,new Stack<>());
        System.out.println(sol());

    }
    static public int sol(){
        int ans = 0;
        for(int[] l : loc){
            int[][] a = getArr();
            int tempAns = 0;

            for(int i=0;i<n;i++){
                tempAns += kill(l,a);
                moveDownArr(a);
            }

            ans = Math.max(ans,tempAns);

        }
        return ans;
    }

    static public int kill(int[] l,int[][] a){
        int cnt = 0;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] ch = new boolean[n+1][m];
        for(int ll : l){
            int[] f = findByBFS(ll,a);
            if(f[0]==-1) continue;
            if(!ch[f[0]][f[1]]){
                ch[f[0]][f[1]] = true;
                q.add(f);
            }
        }

        while(!q.isEmpty()){
            int[] temp = q.poll();
            a[temp[0]][temp[1]] = 0;
            cnt++;
        }
        return cnt;
    }

    static public int[][] getArr(){
        int[][] a = new int[n+1][m];

        for(int i=0;i<n+1;i++){
            for(int j=0;j<m;j++){
                a[i][j] = arr[i][j];
            }
        }
        return a;
    }


    static public int[] findByBFS(int x,int[][] a){
        int[] ret = new int[2];
        boolean[][] visited = new boolean[n+1][m];
        visited[n][x] = true;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n,x});

        while(!q.isEmpty()){
            int[] temp = q.poll();

            if(a[temp[0]][temp[1]] == 1){
                ret[0] = temp[0];
                ret[1] = temp[1];
                return ret;
            }

            for(int i=0;i<4;i++){
                int nx = temp[0] + dir[i][0];
                int ny = temp[1] + dir[i][1];

                if(nx >= 0 && nx < n+1 && ny >= 0 && ny < m && !visited[nx][ny]
                        && (Math.abs(nx-n) + Math.abs(ny-x))<= d ){
                    visited[nx][ny] = true;
                    q.add(new int[]{nx,ny});
                }

            }

        }


        return new int[]{-1,-1};
    }

    static public void moveDownArr(int[][] a){
        int[][] temp = new int[n+1][m];
        for(int i=0;i<n+1;i++){
            for(int j=0;j<m;j++){
                temp[i][j] = a[i][j];
            }
        }
        for(int i=1;i<n+1;i++){
            for(int j=0;j<m;j++){
                a[i][j] = temp[i-1][j];
            }
        }
        for(int j=0;j<m;j++) {
            a[0][j] = 0;
            a[n][j] = 0;
        }

    }


    static public void mC3(int idx, Stack<Integer> list){
        if(list.size() == 3){
            int[] temp = new int[3];
            for(int i=0;i<3;i++){
                temp[i] = list.get(i);
            }
            loc.add(temp);
            return;
        }
        if(idx >= m ) return;

        list.add(idx);
        mC3(idx+1,list);
        list.pop();
        mC3(idx+1,list);
    }




    static class MyScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int nextInt() throws IOException {
            if(!st.hasMoreElements()){
                st = new StringTokenizer(br.readLine());
            }
            return Integer.parseInt(st.nextToken());
        }
    }
}