17135_캐슬 디펜스 !!!

아니 왜 안 되는 거야

1. 예제 잘 나옴

2. 질문 게시판 돌아다니면서 반례 넣으면 정답 잘 출력

 

> 근데???? 26%에서 틀린다고 나온다...

 

package ssafyAlgorithm;

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

public class Main_bj_17135_캐슬디펜스_list {

    static int n,m,d, map[][];
//    static ArrayList<int[]>[] enemies; //적의 위치 저장
    static int ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        d = sc.nextInt();

        map = new int[n+1][m]; //n번째 줄은 궁수 넣기
        
        ArrayList<int[]>[] enemies; //적의 위치 저장
        enemies = new ArrayList[n]; //n번째 줄에 있는 적은
        for(int i=0; i<n; i++) {
            //{m번 째에 있다, 죽으면 -1, 살아있으면 8282}
            enemies[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //1: 적
                map[i][j] = sc.nextInt();
                if(map[i][j] == 1) {
                    enemies[i].add(new int[] {j, 8282});
                }
            }
        }
        //입력 끝

//      int remainTime = n-1; // -1이 되면 게임 끝
        //순조부로 자리 3개 고르고, 시뮬레이션 돌려서 ans 계속 갱신
        boolean[] pickWarrior = new boolean[m];
        int[] warriors = new int[3];
        chooseWarriors(0,0, pickWarrior, warriors, enemies);

        System.out.println(ans);

    }

    private static void chooseWarriors(int cnt,int idx, boolean[] pickWarrior, int[] warriors, ArrayList<int[]>[] enemies) {
        if(cnt == 3) {
        	//arraylist 초기화가 안 되는 이유를 모르겠음...어쨌든 초기화가 필요함
        	for(int i=0; i<enemies.length; i++) {
        		for(int j=0; j<enemies[i].size(); j++) {
        			enemies[i].get(j)[1] = 8282;
        		}
        	}
        	
            gameStart(warriors, n-1, enemies, 0);
            return;
        }

        for(int i=idx; i<m; i++) { //조합...
            if(!pickWarrior[i]) {
                pickWarrior[i] = true;
                warriors[cnt] = i;
                chooseWarriors(cnt+1,i+1, pickWarrior, warriors, enemies);
                pickWarrior[i] = false;
            }
        }
    }

    private static void gameStart(int[] warriors, int line, ArrayList<int[]>[] enemies, int killCnt) {
        if(line < 0) {
            ans = Math.max(ans, killCnt);
            return;
        }

        int[][] killEnemy = new int[3][2]; //동시에 죽여야 되니까 뭐....
//      for (int i = 0; i < 3; i++) {
//          Arrays.fill(killEnemy[i], -1);
//      }

        for(int w=0; w<3; w++) {
//          워리어 위치: {line+1, warriors[w]}
//          적은 i=line~0 (--)
//          gameStart(warriors, line-1, enemies, killCnt+여기서죽인놈(0~3));

            
            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            	if(o1[2] != o2[2]) return o1[2] - o2[2]; //거리 짧은 순
            	else return o1[1] - o2[2]; //왼쪽에 붙은 순
            });
            
            for (int i = line; i>=0; i--) {
                for(int j=0; j<enemies[i].size(); j++) {
                	if(enemies[i].get(j)[1] == 8282) {
                		int chai = chaiCal(line+1,warriors[w], i,enemies[i].get(j)[0]);
                		pq.add(new int[] {i, enemies[i].get(j)[0], chai});
                	}
                }
            }
            
            int[] nearest = null;
            if(pq.isEmpty()) {
            	killEnemy[w][0] = -1;
            	killEnemy[w][1] = -1;
            } else {
            	nearest = pq.poll();
            	if(nearest[2] <= d) {
                	killEnemy[w][0] = nearest[0];
                	killEnemy[w][1] = nearest[1];
                }
                else {
                	killEnemy[w][0] = -1;
                	killEnemy[w][1] = -1;
                }
            }
        }

        // 동시에 죽이기
        int kills = 0;
//        System.out.println("궁수 자리: "+Arrays.toString(warriors));
        for (int i = 0; i < 3; i++) {
//        	System.out.println(Arrays.toString(killEnemy[i]));
            if(killEnemy[i][0] == -1 && killEnemy[i][1] == -1) continue;

            int row = killEnemy[i][0];
            int col = killEnemy[i][1];

            for(int[] eCol: enemies[row]) {
                if(eCol[0] == col) {
                    if(eCol[1] == 8282) {
                        eCol[1] = -1;
                        kills++;
                    }
                    break;
                }
            }
//          if(enemies2[row].ge)
        }

        gameStart(warriors, line-1, enemies, killCnt+kills);

    }

    private static int chaiCal(int i, int j, int i2, int j2) {
        int x = Math.abs(i-i2);
        int y = Math.abs(j-j2);
        return x+y;
    }

}

 

 

안 되는 이유  찾음!!

사용 알고리즘: 빡!구현, 순조부, dfs?

사용 언어: java

 

 

통과된 코드

package ssafyAlgorithm;

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

public class Main_bj_17135_캐슬디펜스_list {

    static int n,m,d, map[][];
    static int ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); //세로(궁수 자리 때문에 +1)
        m = sc.nextInt(); //가로
        d = sc.nextInt(); //사정 거리

        map = new int[n+1][m]; //n번째 줄은 궁수 넣기
        ArrayList[] enemies = null;
        enemies = new ArrayList[n]; //n번째 줄에 있는 적은
        for(int i=0; i<n; i++) {
            //{m번 째에 있다, 죽으면 -1, 살아있으면 8282}
            enemies[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //1: 적
                map[i][j] = sc.nextInt();
                if(map[i][j] == 1) {
                    enemies[i].add(new int[] {j, 8282});
                }
            }
        }
        //입력 끝

//      int remainTime = n-1; // -1이 되면 게임 끝
        //순조부로 자리 3개 고르고, 시뮬레이션 돌려서 ans 계속 갱신
        boolean[] pickWarrior = new boolean[m];
        int[] warriors = new int[3];
        chooseWarriors(0,0, pickWarrior, warriors, enemies);

        System.out.println(ans);

    }

    private static void chooseWarriors(int cnt,int idx, boolean[] pickWarrior, int[] warriors, ArrayList<int[]>[] enemies) {
        if(cnt == 3) {
        	//arraylist 초기화가 안 되는 이유를 모르겠음...어쨌든 초기화가 필요함
        	for(int i=0; i<enemies.length; i++) {
        		for(int j=0; j<enemies[i].size(); j++) {
        			enemies[i].get(j)[1] = 8282;
        		}
        	}
        	
            gameStart(warriors, n-1, enemies, 0);
            return;
        }

        for(int i=0; i<m; i++) { //조합...
            if(!pickWarrior[i]) {
                pickWarrior[i] = true;
                warriors[cnt] = i;
                chooseWarriors(cnt+1,i+1, pickWarrior, warriors, enemies);
                pickWarrior[i] = false;
            }
        }
    }

    private static void gameStart(int[] warriors, int line, ArrayList<int[]>[] enemies, int killCnt) {
        if(line < 0) {
            ans = Math.max(ans, killCnt);
            return;
        }

        int[][] killEnemy = new int[3][2]; //동시에 죽여야 되니까, 배열에 저장해놓고 한 번에 죽이기

        for(int w=0; w<3; w++) {
//          워리어 위치: {line+1, warriors[w]}
//          적은 i=line~0 (--)
//          gameStart(warriors, line-1, enemies, killCnt+여기서죽인놈(0~3));

            
            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            	if(o1[2] != o2[2]) return o1[2] - o2[2]; //거리 짧은 순
            	else return o1[1] - o2[1]; //왼쪽에 붙은 순
            });
            
            for (int i = line; i>=0; i--) {
                for(int j=0; j<enemies[i].size(); j++) {
                	if(enemies[i].get(j)[1] == 8282) {
                		int chai = chaiCal(line+1,warriors[w], i,enemies[i].get(j)[0]);
                		pq.add(new int[] {i, enemies[i].get(j)[0], chai});
                	}
                }
            }
            
            int[] nearest = null;
            if(pq.isEmpty()) {
            	killEnemy[w][0] = -1;
            	killEnemy[w][1] = -1;
            } else {
            	nearest = pq.poll();
            	if(nearest[2] <= d) {
                	killEnemy[w][0] = nearest[0];
                	killEnemy[w][1] = nearest[1];
                }
                else {
                	killEnemy[w][0] = -1;
                	killEnemy[w][1] = -1;
                }
            }
        }

        // 동시에 죽이기
        int kills = 0;
        for (int i = 0; i < 3; i++) {
            if(killEnemy[i][0] == -1 && killEnemy[i][1] == -1) continue;

            int row = killEnemy[i][0];
            int col = killEnemy[i][1];

            for(int[] eCol: enemies[row]) {
                if(eCol[0] == col) {
                    if(eCol[1] == 8282) {
                        eCol[1] = -1;
                        kills++;
                    }
                    break;
                }
            }
        }

        gameStart(warriors, line-1, enemies, killCnt+kills);

    }

    private static int chaiCal(int i, int j, int i2, int j2) {
        int x = Math.abs(i-i2);
        int y = Math.abs(j-j2);
        return x+y;
    }

}

 

위의 코드와 어떤 게 다르냐!

 

PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
             if(o1[2] != o2[2]) return o1[2] - o2[2]; //거리 짧은 순
             else return o1[1] - o2[1]; //왼쪽에 붙은 순
            });

 

코드가 길어지다 보니, 오타가 난 듯하다. 위의 코드에서는 해당 부분이 else return o1[1] - o2[2]; 라고 되어 있을 것이다.

아 진짜 어이가 없군~!