[백준] 17135 - 캐슬 디펜스

문제

 

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

 

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

 

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

 

풀이 방법

1. 조합으로 궁수 3명이 올 수 있는 x좌표 찾기

2. 공격 (궁수는 동시에 공격, 거리가 D이하인 적 중 가장 가까운 적, 그런 경우가 여럿일 땐 가장 왼쪽)

   - 공격받은 적의 위치를 저장할 리스트 (같은 적이 여러 궁수에게 공격 당할 수 있기 때문에 처리 먼저)

   - 그림처럼 궁수 바로 위(파란 칸)에 적이 있다면 bfs 필요 X

      -> 공격받은 적의 위치를 저장하는 리스트에 저장만 함

   - 궁수 바로 위(파란 칸)에 적이 없다면 bfs 진행

      -> Node클래스를 이용(y좌표, x좌표, 궁수와의 거리), PriorityQueue 이용

      -> pq에서 poll할 때 거리가 D보다 작고 1이면 공격할 수 있는 적이므로 리스트에 저장

   - 각 궁수 위치에서 계산 후 공격받은 적의 위치를 가지고 있는 리스트에서 공격 받은 적 count, map에서 0으로 변경

     주의! 같은 적이 두번 공격 받아도 한번만 count!!

3. 궁수의 y좌표를 감소시키며 궁수의 y좌표가 1일때까지 반복

4. 조합으로 궁수 3명이 올 수 있는 경우에서 공격을 모두 한 후 가장 큰 count값 출력

 

내 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_17135 {
	static int N, M, D, max=Integer.MIN_VALUE;
	static int[][] map;
	static int[] castle;
	
	static int[] dy = {0,-1,0};	//좌, 상, 우
	static int[] dx = {-1,0,1};
	
	static class Node implements Comparable<Node>{
		int y,x,dis;

		public Node(int y, int x, int dis) {
			super();
			this.y = y;
			this.x = x;
			this.dis = dis;
		}

		@Override
		public int compareTo(Node o) {
			return this.dis==o.dis ? this.x-o.x : this.dis-o.dis;
		}

		@Override
		public String toString() {
			return "Node [y=" + y + ", x=" + x + "]";
		}
		
		
	}
	
	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];
		castle = new int[3];
		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());
			}
		}
		
		combi(0, 0);
		System.out.println(max);
		
		br.close();	
	
	}
	
	private static void combi(int cnt, int start) {
		if(cnt==3) {
			max = Math.max(max, attack());
			return;
		}
		for (int i = start; i < M; i++) {
			castle[cnt] = i;
			combi(cnt+1, i+1);
		}
	}
	
	private static int attack() {
		int cnt = 0;
		int n = N;
		int[][] newMap = new int[N][M];
		copy(map, newMap);
		
		while(n>0) {
			//공격받은 적 저장, 궁수 3명이 모두 공격 후 newMap update
			List<Point> attacked = new ArrayList<>();
			//각 궁수 위치에서 공격
			for (int i = 0; i < 3; i++) {
				if(newMap[n-1][castle[i]]==1) {	//내 바로 앞에 있는 경우
					attacked.add(new Point(castle[i], n-1));
				}
				else {	//내 바로 앞에 없는 경우는 탐색 시작
					boolean[][] visited = new boolean[N][M];
					PriorityQueue<Node> pq = new PriorityQueue<>();
					
					pq.offer(new Node(n-1, castle[i], 1));
					visited[n-1][castle[i]] = true;
					
					while(!pq.isEmpty()) {
						Node cur = pq.poll();

						if(cur.dis>0 && cur.dis<=D && newMap[cur.y][cur.x]==1) {
							//공격 성공!
							attacked.add(new Point(cur.x, cur.y));
							break;
						}
						for (int d = 0; d < 3; d++) {
							int ny = cur.y + dy[d];
							int nx = cur.x + dx[d];

							if(ny<0 || ny>=N || nx<0 || nx>=M) continue;
							if(visited[ny][nx]) continue;

							int dis = Math.abs(n-ny) + Math.abs(castle[i]-nx);
							pq.offer(new Node(ny, nx, dis));
							visited[ny][nx] = true;
						}
					}
				}
			}
			for (int i = 0; i < attacked.size(); i++) {
				int y = attacked.get(i).y;
				int x = attacked.get(i).x;
				if(newMap[y][x] == 0) continue;
				cnt++;
				newMap[y][x] = 0;
			}
			//궁수를 올림! -> 1까지만
			n--;
		}
		return cnt;
	}
	
	private static void copy(int[][] map, int[][] newMap) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				newMap[i][j] = map[i][j];
			}
		}
	}
}