🔗문제 링크
🔒 문제 설명
격자판(NxM)형태에 적이 존재할 때, (N+1)행에 궁수 3명을 배치하여 적을 막으려 한다.
궁수와 적과의 거리는 "맨해튼 거리"로 계산한다.
거리가 D이하인 적중 가장 가까운 적을 공격하며, 그러한 적이 여럿일 경우에는 가장 왼쪽의 적을 공격한다. (따라서 같은 적을 여러 궁수가 공격할 수 있다.)
각 궁수의 공격 1회가 끝나면 적들은 아래로 한칸 이동하며, 이미 마지막 행인 경우 게임에서 제외된다.
모든적이 격자판에서 제외되면 게임이 끝난다.
이때 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산한다.
🧾 입력 예시
5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0첫번째 줄에는 격자판의 행(N),열(M), 그리고 궁수의 사거리 D가 주어진다.
두번째 줄부터 격자판이 주어진다.
🔎 출력 예시
5
🔑 문제 풀이
-
궁수들의 열위치를 담을 colList를 생성한다.
-
궁수들의 위치를 DFS(deployArcher())를 통하여 만든다.
-
정해진 위치에 따라 디펜스를 시작(defense())한다.
-
findEnemy()를 통하여 각 궁수가 잡을 적의 위치를 찾은 후 enemyList에 추가해준다.
-
killEnemy()를 통하여 중복된 경우를 제외하고 죽인 적의 수를 찾는다.
-
2 ~ 5번 과정을 반복하여 모든 배치에 따른 kill수를 찾아 최대값을 반환한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
Main z = new Main();
z.solution();
}
int N = 0;
int M = 0;
int D = 0;
int answer = 0;
private void solution() 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());
answer = Integer.MIN_VALUE;
int[][] map = new int[N][M];
for(int i=0 ; i<map.length ; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0 ; j<map[0].length ; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
List<Integer> colList = new ArrayList<>();
deployfArcher(map, colList, -1);
System.out.println(answer);
}
private void deployfArcher(int[][] map, List<Integer> colList, int befo) {
if(colList.size()==3) {
int[][] cMap = copyMap(map);
int kill = defense(cMap, colList);
answer = Math.max(answer, kill);
return;
}
for(int i=befo+1 ; i<M ; i++) {
colList.add(i);
deployfArcher(map,colList,i);
colList.remove(colList.size()-1);
}
}
private int defense(int[][] map, List<Integer> archerList) {
int kill = 0;
// System.out.println(archerList);
for(int time=1 ; time<=N ; time++) {
List<int[]> enemyList = new ArrayList<>();
for(int archerCol : archerList) {
int[] pos = findEnemy(map,archerCol);
if(pos[0]!=-1)
enemyList.add(pos);
}
int temp = killEnemy(map, enemyList);
// System.out.printf("time %d : %d\n",time,temp);
// printMap(map);
kill += temp;
moveEnemy(map);
}
// System.out.println("kill = "+kill);
// System.out.println();
return kill;
}
private int[] findEnemy(int[][] map, int archerCol) {
int[] pos = new int[2];
Arrays.fill(pos, -1);
int minDist = Integer.MAX_VALUE;
for(int i=N-1 ; i>=0 ; i--) {
for(int j=0 ; j<M ; j++) {
if(map[i][j]==1) {
// 적이 있는 위치
int dist = getDist(i,j,archerCol);
if(dist<=D) {
if(dist<minDist) {
pos[0] = i;
pos[1] = j;
minDist = dist;
}else if (dist==minDist) {
if(j<pos[1]) {
pos[0] = i;
pos[1] = j;
}
}
}
}
}
}
return pos;
}
private int getDist(int row, int col, int archerCol) {
int len = 0;
len = (N-row) + Math.abs(archerCol-col);
return len;
}
private int killEnemy(int[][] map, List<int[]> enemyList) {
int kill = 0;
for(int[] pos : enemyList) {
int row = pos[0];
int col = pos[1];
if(map[row][col]!=0) {
map[row][col] = 0;
kill++;
}
}
return kill;
}
private void moveEnemy(int[][] map) {
for(int j=0 ; j<M ; j++) {
map[N-1][j] = 0;
}
for(int i=N-1 ; i>0 ; i--) {
for(int j=0 ; j<M ; j++) {
map[i][j] = map[i-1][j];
}
}
for(int j=0 ; j<M ; j++) {
map[0][j] = 0;
}
}
private int[][] copyMap(int[][] map){
int[][] copyOfMap = new int[N][M];
for(int i=0 ; i<N ; i++) {
for(int j=0 ; j<M ; j++) {
copyOfMap[i][j] = map[i][j];
}
}
return copyOfMap;
}
private void printMap(int[][] map) {
for(int[] arr : map) {
System.out.println(Arrays.toString(arr));
}
}
}
📇 결과
