[BOJ 17135] 캐슬 디펜스 (Java)

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

17135번: 캐슬 디펜스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BOJ_17135 {
	static class Enemy implements Comparable<Enemy>{
		int r, c, dist;
		Enemy(int r, int c, int dist){
			this.r=r;
			this.c=c;
			this.dist=dist;
		}
		@Override
		public int compareTo(Enemy o) {
			if (this.dist==o.dist) {
				return this.c-o.c;
			}
			return this.dist-o.dist;
		}
	}
	static int N, M, D;
	static int[][] map;
	static int answer=0;
	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());
		map=new int[N][M];
		for (int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		comb(0, 0, 3, new int[3][2]);
		System.out.println(answer);
	}
	private static void comb(int cnt, int start, int n, int[][] archers) {
		if (cnt==n) {
			play(archers);
			return;
		}
		for (int i=start; i<M; i++) {
			archers[cnt][0]=N;
			archers[cnt][1]=i;
			comb(cnt+1, i+1, n, archers);
		}
		
	}
	private static void play(int[][] archers) {
		int[][] cMap=new int[N][M];
		int died=0;
		for (int i = 0; i < N; i++) {
			cMap[i]=Arrays.copyOf(map[i], M);
		}
		while (true) {
			ArrayList<int[]> enemies=getEnemy(cMap);
			if (enemies.size()==0) {
				answer=Math.max(answer, died);
				break;
			}
			for (int i=0; i<3; i++) {
				Enemy toKill=killEnemy(archers[i][0], archers[i][1], enemies);
				if (toKill!=null) {
					int er=toKill.r;
					int ec=toKill.c;
					if (cMap[er][ec]==1) {
						cMap[er][ec]=0;
						died++;
					}
				}
			}
			moveEnemy(cMap);
		}
		
	}
	private static ArrayList<int[]> getEnemy(int[][] cMap) {
		ArrayList<int[]> enemies=new ArrayList<>();
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				if (cMap[i][j]==1) enemies.add(new int[] {i,j});
			}
		}
		return enemies;
	}
	
	private static Enemy killEnemy(int archer_r, int archer_c, ArrayList<int[]> enemies) {
		PriorityQueue<Enemy> pq=new PriorityQueue<>();
		for (int[] enemy : enemies) {
			int dist= Math.abs(archer_r-enemy[0])+Math.abs(archer_c-enemy[1]);
			if (dist<=D)
				pq.add(new Enemy(enemy[0], enemy[1], dist));
		}
		return pq.poll();
	}
	
	private static void moveEnemy(int[][] cMap) {
		for (int i=N-2; i>=0; i--) {
			for (int j=0; j<M; j++) {
				cMap[i+1][j]=cMap[i][j];
			}
		}
		Arrays.fill(cMap[0], 0);
	}

}

killEnemy를 고를 때 다 탐색 안해줘도 되고, BFS를 써서 원하는 값이 바로 튀어나오게 구현가능하다. 

나는 killEnemy고를때 다 넣고+priority queue를 이용해서 제일 처음에 존재하는 enemy를 죽이도록 했는데, 이럴 필요 없이 BFS를 이용해줘도 된다. 

 

아래 코드는 최대한 최적화 시킨 코드이다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BOJ_17135 {
	static int[] dr= {0, -1, 0};
	static int[] dc= {-1, 0, 1};
	static int N, M, D;
	static int[][] map;
	static int answer=0;
	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());
		map=new int[N][M];
		for (int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		comb(0, 0, 3, new int[3][2]);
		System.out.println(answer);
	}
	private static void comb(int cnt, int start, int n, int[][] archers) {
		if (cnt==n) {
			play(archers);
			return;
		}
		for (int i=start; i<M; i++) {
			archers[cnt][0]=N;
			archers[cnt][1]=i;
			comb(cnt+1, i+1, n, archers);
		}
		
	}
	private static void play(int[][] archers) {
		int[][] cMap=new int[N][M];
		int died=0;
		int archer_pos=N;
		for (int i = 0; i < N; i++) {
			cMap[i]=Arrays.copyOf(map[i], M);
		}
		while (archer_pos>0) {
			int[][] kills=new int[3][2];
			for (int i=0; i<3; i++) {
				int[] toKill=killEnemy(archer_pos, archers[i][1], cMap);
				kills[i]=toKill;
			}
			for (int i=0; i<3; i++) {
				if (kills[i]==null) continue;
				int er=kills[i][0];
				int ec=kills[i][1];
				if (cMap[er][ec]==1) {
					cMap[er][ec]=0;
					died++;
				}
			}
			answer=Math.max(answer, died);
			archer_pos--;
		}
		
	}
	
	private static int[] killEnemy(int archer_r, int archer_c, int[][] cMap) {
		int[] toKill=null;
		Queue<int[]> q=new LinkedList<>();
		boolean[][] visited=new boolean[N][M];
		q.add(new int[] {archer_r, archer_c});
		while (!q.isEmpty()) {
			int[] curr=q.poll();
			int r=curr[0];
			int c=curr[1];
			if (r!=N && cMap[r][c]==1 && Math.abs(r-archer_r)+Math.abs(c-archer_c)<=D) {
				toKill=new int[2];
				toKill[0]=r;
				toKill[1]=c;
				break;
			}
			for (int i=0; i<3; i++) {
				int nr=r+dr[i];
				int nc=c+dc[i];
				if (nr<0 || nc<0 || nr>=archer_r || nc>=M || visited[nr][nc]) continue;
				if (Math.abs(nr-archer_r)+Math.abs(nc-archer_c)<=D) {
					visited[nr][nc]=true;
					q.add(new int[] {nr, nc});	
				}
			}
		}
		return toKill;
	}
	

}

 

여기서는 적이 아래쪽으로 움직이는 것을 궁수의 행 위치를 위로 움직이는 걸로 대신해준다. 그리고 궁수의 행 위치가 0이 되면 게임이 종료된다. <- 이 아이디어를 얻으면 countMap 할 필요도 없다.. 

 

죽일 적은 BFS로 찾아준다. 궁수의 현재 위치를 중심으로 좌, 상, 하 부분으로 움직여주면 된다.

큐에서 뽑은 값이 1이 나올 경우 그것이 죽일 적이므로, 적의 위치를 리턴한다.

큐 탐색을 좌,상,우 부분으로 해주었고 BFS 탐색을 이용해서 가장 좌측에 있는 가장 적은 거리를 갖는 적을 구할 수 있다.

 

여기서 탐색 방향을 3가지로 하는 이유는 하쪽 부분을 탐색해봤자 어차피 안되는 case 만 나오기 때문이다.