알고리즘 문제풀이/BOJ
[BOJ] 삼성 sw 역량 테스트 A형 기출 :: 백준 17135번 캐슬 디펜스 (조합, 시뮬레이션)
- -
BOJ 17135번 캐슬 디펜스 문제 자바(java) 풀이
- 랭크 : 골드4
- 삼성 SW 역량 테스트 A형 기출문제
- 백준 17135번 캐슬 디펜스
문제정리
- 게임 맵은 NxM 크기이다. 1x1 크기의 칸으로 이루어져 있다.
- 각 칸에 포함된 적의 수는 최대 하나이다.
- 격자판 N+1번 행의 모든 칸에는 성이 있다.
- 궁수 3명을 배치하려고 함
4.1 궁수는 성이 있는 칸에 배치 가능. 하나의 칸에는 최대 1명의 궁수만 있을 수 있음
4.2 턴 마다 궁수는 적 하나 공격 가능. 모든 궁수는 동시에 공격
4.3 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적. 그러한 적이 여럿이면 가장 왼쪽에 있는 적 공격
4.4 공격받은 적은 게임에서 제외 - 궁수의 공격이 끝나면 적이 이동한다.
적은 아래로 한칸 이동. 성이 있는 칸으로 이동한 경우 게임에서 제외 - 모든 적이 격자판에서 제외되면 게임 over
-
격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수 계산
-
격자판 상태
0: 빈칸
1: 적
문제풀이
이 문제는 모든 문제가 그렇지만 문제를 잘 읽고 시작해야 합니다.
중요한 점은 적과의 거리가 우선이고 같은 거리에 있는 적이 여러명 있다면 그중 가장 왼쪽에 있는 적을 처치합니다.
가장 왼쪽의 적을 골라내기 위해서 sorting을 진행하면 됩니다.
- width의 크기 중에 3 곳을 뽑는 모든 경우를 따져주어야 한다.
크기가 4라면 (012), (013), (023), (123) 총 4가지가 가능하다. (4C3) - 배치를 하고 거리 D 안에 드는 적 들중 가장 왼쪽의 적(열의 index가 가장 작은 곳에 있는 적)들을 찾는다.
거리가 우선이고 왼쪽 부터 찾으면 됩니다. 거리 1일때 부터 적을 찾아나갑니다.
거리가 1일때 찾지 못했다면 거리2,3.. D까지 찾아갑니다.
거리가 1인 곳은 1곳, 2인 곳은 3곳, 3인 곳은 5곳, N인 곳은 2N-1 구역이 있습니다. 이를 이용해 최적화합니다.
거리가 2인 곳에서 적을 찾았다면 거리가 2인 곳에 있는 적 모두를 찾습니다.(위치 저장)
그래서 적들의 위치를 행위치 기준 정렬하여 맨 왼쪽에 있는 적을 찾아 제거하면 됩니다. - 적의 위치를 아래로 한 칸 내린다.
- 모든 적이 N=1로 사라질때까지 반복한다. 이를 배치 가능한 모든 경우에 대하여 반복한다.
- map의 초기 상태를 기억하기 위해 복사해서 사용한다.
- 자세한 내용은 주석에 달아두었으니 참고하시기 바랍니다!
- 문제를 거의 다 풀어서 생각이 낫는데 bfs로 탐색하는 것도 가능할 것 같습니다 (왼쪽, 위, 오른쪽 탐색)
캐슬 디펜스 자바(java) 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.BufferedReader; | |
| import java.io.IOException; | |
| import java.io.InputStreamReader; | |
| import java.util.List; | |
| import java.util.ArrayList; | |
| import java.util.Comparator; | |
| import java.util.Collections; | |
| class Pos implements Comparable<Pos>{ | |
| int x; | |
| int y; | |
| Pos(int x, int y){ | |
| this.x = x; | |
| this.y = y; | |
| } | |
| @Override | |
| public int compareTo(Pos p){ | |
| if(this.y < p.y) | |
| return -1; | |
| else if(this.y > p.y) | |
| return 1; | |
| return 0; | |
| } | |
| } | |
| class Main { | |
| static int height, width, D; | |
| static int[][] map; | |
| static int max; | |
| static int enemy = 0; | |
| static List<Integer> archers; | |
| public static void main(String[] args) throws IOException{ | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| // 행의 수, 열의 수, 공격 제한 거리 입력 받기 | |
| String[] temp = br.readLine().split(" "); | |
| height = Integer.parseInt(temp[0]); | |
| width = Integer.parseInt(temp[1]); | |
| D = Integer.parseInt(temp[2]); | |
| map = new int[height][width]; | |
| // 격자판의 상태 입력 받기 | |
| for(int i=0; i<height; i++){ | |
| temp = br.readLine().split(" "); | |
| for(int j=0; j<width; j++){ | |
| int t = Integer.parseInt(temp[j]); | |
| map[i][j] = t; | |
| if(t == 1) | |
| enemy++; | |
| } | |
| } | |
| max = 0; | |
| archers = new ArrayList<>(); | |
| // 궁수를 놓는 모든 조합 찾기 | |
| comb(0,width,3); | |
| System.out.println(max); | |
| br.close(); | |
| } | |
| private static void comb(int start, int N, int r){ | |
| if(r==0){ | |
| int kill = solve(); | |
| max = max < kill ? kill : max; | |
| return; | |
| } | |
| for(int i=start; i<N; i++){ | |
| archers.add(i); | |
| comb(i+1, N, r-1); | |
| archers.remove(archers.size()-1); | |
| } | |
| } | |
| private static int solve(){ | |
| int run = 0; | |
| int[][] copy = deepCopy(map); | |
| int kill = 0; | |
| List<Pos> killed, killed2, killed3; | |
| // 모든 적이 없어질때까지 턴 반복 | |
| while(run + kill != enemy){ | |
| killed = new ArrayList<>(); | |
| killed2 = new ArrayList<>(); | |
| killed3 = new ArrayList<>(); | |
| boolean flag; // 적 발견시 dist를 증가시켜 탐색하지 않고 while문 탈출을 위한 flag | |
| // 궁수들의 적 탐색 | |
| for(int i=0; i<archers.size(); i++){ | |
| int idx = archers.get(i); | |
| flag = false; | |
| int dist = 1; | |
| // 거리를 늘려가며 적을 찾거나 거리가 D를 넘기 전까지 반복하며 탐색 | |
| while(true){ | |
| int temp = 0; | |
| // 거리가 작은 것, 왼쪽 아래부터 탐색 | |
| for(int j=height-1; j>=0; j--){ | |
| for(int k=0; k<width; k++){ | |
| // 거리 1부터 D까지 | |
| if(getDistance(height, idx, j, k) == dist){ | |
| temp++; // dist내에서 찾을 수 있는 곳의 개수 check | |
| // 적이 있다면 제거하기 위한 리스트에 넣기 | |
| if(copy[j][k] == 1){ | |
| switch(i){ | |
| // 1번 궁수 | |
| case 0: | |
| killed.add(new Pos(j,k)); | |
| break; | |
| // 2번 궁수 | |
| case 1: | |
| killed2.add(new Pos(j,k)); | |
| break; | |
| // 3번 궁수 | |
| case 2: | |
| killed3.add(new Pos(j,k)); | |
| } | |
| flag = true; // 적 발견시 true로 설정 | |
| } | |
| } | |
| } | |
| // 거리 dist에서 탐색 해야할 수 = dist*2-1 (1,3,5,7,...) | |
| // 적을 찾아도 같은 거리내의 모든 적을 찾기 => 가장 왼쪽의 적을 찾기 위해서 | |
| if(temp == dist*2-1) | |
| break; | |
| } | |
| dist++; | |
| // 적을 찾은 경우 다른 궁수 탐색 | |
| if(flag) | |
| break; | |
| // D보다 작은 거리만 탐색 | |
| if(dist > D) | |
| break; | |
| } | |
| } | |
| // 행 기준 정렬 | |
| Collections.sort(killed); | |
| Collections.sort(killed2); | |
| Collections.sort(killed3); | |
| // 각 궁수가 찾은 가장 왼쪽 적 제거 | |
| if(killed.size() != 0){ | |
| Pos p1 = killed.get(0); | |
| if(copy[p1.x][p1.y] == 1){ | |
| copy[p1.x][p1.y] = 0; | |
| kill++; | |
| } | |
| } | |
| if(killed2.size() != 0){ | |
| Pos p2 = killed2.get(0); | |
| if(copy[p2.x][p2.y] == 1){ | |
| copy[p2.x][p2.y] = 0; | |
| kill++; | |
| } | |
| } | |
| if(killed3.size() != 0){ | |
| Pos p3 = killed3.get(0); | |
| if(copy[p3.x][p3.y] == 1){ | |
| copy[p3.x][p3.y] = 0; | |
| kill++; | |
| } | |
| } | |
| // 맨 밑에줄에 있는 적은 제외 시키기 | |
| for(int i=0; i<width; i++){ | |
| if(copy[height-1][i] == 1){ | |
| copy[height-1][i] = 0; | |
| run++; | |
| } | |
| } | |
| // 밑으로 하나씩 이동 시키기 | |
| for(int i=height-2; i>=0; i--){ | |
| for(int j=0; j<width; j++){ | |
| if(copy[i][j] == 1){ | |
| copy[i+1][j] = 1; | |
| copy[i][j] = 0; | |
| } | |
| } | |
| } | |
| } | |
| return kill; // 죽인 적의 수 return | |
| } | |
| // 배열 복사 | |
| private static int[][] deepCopy(int[][] src){ | |
| int[][] dest = new int[src.length][src[0].length]; | |
| for(int i=0; i<src.length; i++) | |
| System.arraycopy(src[i], 0, dest[i], 0, src[i].length); | |
| return dest; | |
| } | |
| // 두 점의 거리 구하기 | |
| private static int getDistance(int x, int y, int x2, int y2){ | |
| return Math.abs(x-x2) + Math.abs(y-y2); | |
| } | |
| } |
반례
-
반례1
10 10 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ans: 30 -
반례2
5 5 2 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 ans 14 -
반례3
5 5 3 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 0 ans 13 -
반례4
10 10 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ans 2 -
반례5
15 15 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ans 0
Contents
소중한 공감 감사합니다