[JAVA] 백준 17135 캐슬 디펜스 풀이

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

17135번: 캐슬 디펜스

 

---

 

풀이 방법

1. 궁수들의 자리를 조합을 이용해 뽑음 

2. 뽑은 자리에서 bfs를 이용해 공격 거리안에 있는 죽일 수 있는 적을 표시함 

3. 한번의 공격이 끝난 후, 표시한 곳을 돌면서 죽인 적의 위치를 0으로 바꿔줌 

4. 적의 위치를 r+1 해줌

5. 2-4를 반복

6. 더이상 적이 없을 경우, 죽인 적의 수와 현재 최대값을 비교 

7. 다음 조합에서 2-6을 반복, 죽일 수 있는 적의 최대값을 구함

 

틀렸던 부분 

1. 처음에 사방탐색만 함 -> 다시 살펴보니 대각선 방향은 사방탐색으로 불가 -> bfs로 변경

2. 같은 적이 여러 궁수에게 공격당할 수 있다.

-> 테케를 돌리는데 답이 자꾸 1만큼 차이가 나서 문제를 다시 읽어보니 같은 적이 여러 궁수에게 공격당할 수 있음

-> 원래 죽일 수 있는 적을 발견하자마자 값을 0으로 바꿔줬는데

    코드를 수정해 적의 위치를 표시하고 공격이 끝난 후, 0으로 바꿔줌  

3. map 초기화를 안해줌 -> ori 배열에 초기 map 정보를 저장하고, 한 조합이 끝날 때 마다 map에 ori 값을 덮어줌

 

Java 최종 코드 

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

public class BOJ_17135_캐슬디펜스 {
	static StringTokenizer st;
	static int N,M,D;
	static ArrayList<Integer> person;
	static int [] pick;
	static int[][] map;
	static int[][] move;
	static int[][] dir= {{0,-1},{-1,0},{0,1}}; //왼쪽부터 탐색, 아래는 x
	static int R=3; //궁수의 수
	static int result;
	static int enemy; 
	static int[][] ori;
	static boolean[][] checked;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		D=Integer.parseInt(st.nextToken());
		map=new int[N+1][M];
		person=new ArrayList<Integer>();
		ori=new int[N+1][M];
		// map
		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());
				ori[i][j]=map[i][j];
			}
		}
		// 궁수 자리 후보 
		for (int j = 0; j < M; j++) {
			person.add(j);
		}
		result=0;
		pick=new int[3];
		combination(0, 0);

		System.out.println(result);
	}
	private static void combination(int cnt, int start) {
		if (cnt==R) {
			attack(pick);
			// 최대 적의 개수 구하기
			result=result<enemy?enemy:result;
			// 맵 초기화!!!
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j]=ori[i][j];
				}
			}
			return;
		}
		for(int i=start; i<M; i++) {
			pick[cnt]=i;
			combination(cnt+1, i+1);
		}
		
	}
	private static void attack(int[] pick) {
		enemy=0;
		int is=0;
		while(true) {
			checked=new boolean [N][M];
			for (int index:pick) {
				int y=person.get(index);
				bfs(N,y);
			} // 한턴 공격 끝
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(checked[i][j]) {
						// 죽임을 당한 적을 map에서 0으로 만듦
						map[i][j]=0;
						enemy+=1;
					}
				}
			}
			// 적 움직임, 마지막행부터 옮기기
			for (int i = N-1; i >=0; i--) {
				for (int j = 0; j < M; j++) {
					if (map[i][j]==1) {
						// 적들은 한칸 밑으로
						if(i+1<N) {
							// 성에 도착하지 않았을 경우에만 옮김
							map[i+1][j]=1;
							is++;
						}map[i][j]=0;
					}
				}
			}
			// 남은 적이 하나도 없을 경우 종료
			if(is==0) break;
			is=0;
		}
	}
	private static void bfs(int x, int y) {
		move=new int[N+1][M];
		Queue<int[]> queue=new LinkedList<int[]>();
		queue.add(new int[] {x,y});
		outer:while(!queue.isEmpty()) {
			int[] list=queue.poll();
			int r=list[0];
			int c=list[1];
			for (int i=0; i<3; i++) {
				// 탐색 어떻게..? bfs?? 
				int nx=r+dir[i][0];
				int ny=c+dir[i][1];
				if(isOkay(nx,ny) && move[nx][ny]==0) {
					move[nx][ny]=move[r][c]+1;
					if (move[nx][ny]>D) break outer;// 공격 거리 안에 있는 적이 없음
					//범위에 있고, 공격거리 안에 있는 적이라면 공격!
					queue.add(new int[] {nx,ny});
					if(map[nx][ny]==1 && move[nx][ny]<=D) {
//						map[nx][ny]=0;// 같은 곳을 공격할 수 있기 때문에 여기서 0으로 만들면 안됨!!! 
						checked[nx][ny]=true;
						break outer; // 한번에 한적만 죽임
					}
				}
			}
		}
	}
	private static boolean isOkay(int r, int c) {
		return r>=0 && c>=0 && r<N && c<M;
	}
}

 

시간은 괜찮은데, 메모리를 다른 사람들보다 훨씬 많이 썼다. 배열을 여러개 써서 그런 것 같다.. 아마도?...

보니까 교수님은 bfs말고 comparable로 값을 비교해가면서 풀었음