[Java] 백준 17135번 : 캐슬 디펜스

1. 문제

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

17135번: 캐슬 디펜스

 

 

 

2. 풀이과정

1. 궁수 3명의 위치에 대해 조합 구하기

2. 각 조합마다 simulation() 실행

[Simulation]

        1.시간이 N(배열의 세로)만큼 지나서 더 봤자 적들이 없는 경우 or 그 전에 적들을 다 물리친 경우 반복 종료

                1-1. 각 궁수마다 bfs로 가장 가까운 적을 찾음 but 찾고 있는 거리가 D보다 커지면 다음 궁수로 넘어감.

                1-2. 가장 가까운 적을 찾으면, -castle(=시간 역할을 하는 값)으로 표기 & 적의 수 1감소

                1-3. 궁수가 -castle값을 본 경우는, 같은 시간에 같은 적을 쏴야하는 경우임

3. simulation 결과값이 최소면 업데이트

 

 

*tip : 적들이 다가오는 것 => 성이 앞으로 한 칸 나가는 것으로 생각하기(시간 단축)

 

 

 

 

[소스코드]

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

public class Boj17135_castleDefense2 {

	static int N, M, D, enemies, result;
	static int[] selected;
	static int[][] map;
	
	public static void combination(int start, int cnt) {
		if(cnt==3) {
			result = Math.max(result, simulation());
			return;
		}
		
		for(int i=start; i<M; i++) {
			selected[cnt] = i;
			combination(i+1, cnt+1);
		}
	}
	
	public static int simulation() {//bfs
		int enemySu = enemies;//적의 수
		int dx[] = {0, -1, 0}, dy[] = {-1, 0, 1};
		//map 복사
		int[][] copyMap = new int[N][M];
		for(int i=0;i<N;i++)
			copyMap[i] = Arrays.copyOf(map[i], M);
		
		//계산
		int castle = N;
		while(enemySu > 0 && castle > 0) {//적이 다 없을 때까지
			for(int i=0;i<3;i++) {//궁수 3명과 가까운 적(중 왼쪽) 찾아 없애기
				//bfs
				Queue<int[]> q = new LinkedList<>();
				q.add(new int[] {castle, selected[i]});//i번째 궁수의 위치 삽입
				boolean visited[][] = new boolean[N][M];//bfs용 방문기록
				int d = 0;//거리
				outloop: while(!q.isEmpty()) {
					if(++d > D)
						break;
					
					for(int k=0, size=q.size(); k<size; k++) {
						int[] node = q.poll();
						for(int j=0; j<3; j++) {//3방향 탐색
							int nx = node[0] + dx[j];
							int ny = node[1] + dy[j];
							if(0<=nx && nx<castle && 0<=ny && ny<M && !visited[nx][ny]) {//범위에 속하면
								if(copyMap[nx][ny]==1) {
									enemySu--;
									copyMap[nx][ny] = -castle;
									break outloop;
								}
								else if(copyMap[nx][ny]== -castle) {
									break outloop;
								}
								visited[nx][ny] = true;
								q.add(new int[] {nx, ny});
							}
						}
					}
				}
			}
			castle--;
		}
		
		return enemies-enemySu;
	}
	
	public static void main(String[] args) throws Exception {
		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());
		selected = new int[3];//궁수 3명의 위치
		map = new int[N][M];
		enemies = 0;//적들의 수
		
		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());
				if(map[i][j] == 1) enemies++;
			}
		}
		
		combination(0, 0);
		System.out.println(result);
	}
}

 

[결과]