[백준 - 17135] 골드4 캐슬디팬스 (구현)

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

1. 유형

조합, bfs, 시뮬레이션

 

2. 풀이

조합을 이용해서 궁수의 위치를 정해준다.

 

궁수의 위치마다 bfs를 돌려준다.

 

적을 찾았으면 동시에 적을 죽여야한다.

 

3. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class back_17135캐슬디펜스 {
	static int M,N,map[][], D, answer=0;
	static int pos[];
	static int dr[]= {0,-1,0};
	static int dc[]= {-1,0,1}; 
	static class Pair{
		int r,c,d;
		public Pair(int r, int c, int d) {
			this.r=r;
			this.c=c;
			this.d=d;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		D = sc.nextInt();
		map = new int[N+1][M];
		pos = new int[3];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		comb(0, 0);
		System.out.println(answer);
	}
	
	static void comb(int idx, int cnt) {
		if(cnt==3) {
			int killenemy=0;
			int tmp_map[][] = new int[N+1][M];
			for (int i = 0; i < N+1; i++) {
				for (int j = 0; j < M; j++) {
					tmp_map[i][j] = map[i][j];
				}
			}
			while(checkMap(tmp_map)) {
				boolean target[][] = new boolean[N][M];
				for (int i = 0; i <3; i++) {
					bfs(target, pos[i], tmp_map);
				}
				//동시에 적 죽이기
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if(target[i][j]==true) {
							tmp_map[i][j] = 0;
							killenemy++;
						}
					}
				}
				//맵 한칸씩 내리기
				for (int i = N; i-1 >= 0 ; i--) {
					for (int j = 0; j < M; j++) {
						tmp_map[i][j] = tmp_map[i-1][j];
					}
				}
				for (int i = 0; i < M; i++) {
					tmp_map[0][i] = 0;
				}
			}
			answer = answer < killenemy ? killenemy:answer;
			return;
		}
		if(idx==M) {
			return;
		}
		pos[cnt] = idx;
		comb(idx+1, cnt+1);
		comb(idx+1, cnt);
	}
	static void bfs(boolean tar[][], int c, int tmp_map[][]) {
		Queue<Pair> q= new LinkedList<>();
		q.add(new Pair(N, c, 0));//궁수자리
		boolean visit[][] = new boolean[N+1][M];
		visit[N][c] = true;
		while(!q.isEmpty()){
			Pair cur = q.poll();
			for (int i = 0; i < 3; i++) {
				int nr = cur.r+dr[i];
				int nc = cur.c+dc[i];
				int nd = cur.d+1;
				if(nr<0||nr>=N||nc<0||nc>=M) continue;
				if(visit[nr][nc]==true) continue;
				if(nd>D) continue;
				if(tmp_map[nr][nc]==1 && nd<=D) {
					tar[nr][nc] = true;
					return;
				}
				visit[nr][nc] = true;
				q.add(new Pair(nr,nc,nd));
			}
		}
	}
	
	static boolean checkMap(int m[][]) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(m[i][j]==1)
					return true;
			}
		}
		return false;
	}
	
}
//dfs를 쓴다
	//while 적이 없을떄까지
		//for 1~3번 궁수 사격준비
			//bfs(i번 차례)
//bfs
	//for 3방향
		//이탈이나 방문 체크
		//거리는 D이하까지만
		//적 찾으면 끝
			//타깃을 정하고 끝

조합을 이용해서 궁수 위치 정하기

pos[cnt] = idx;
comb(idx+1, cnt+1);
comb(idx+1, cnt);

적이 없을 때까지 계속 반복

while(checkMap(tmp_map)) 


	static boolean checkMap(int m[][]) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(m[i][j]==1)
					return true;
			}
		}
		return false;
	}

맵 한칸씩 내리고 마지막 줄은 0으로 초기화

				for (int i = N; i-1 >= 0 ; i--) {
					for (int j = 0; j < M; j++) {
						tmp_map[i][j] = tmp_map[i-1][j];
					}
				}
				for (int i = 0; i < M; i++) {
					tmp_map[0][i] = 0;
				}