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

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

17135번: 캐슬 디펜스

package ssafyjava01;

import java.util.*;

public class P17135 {
	static int N, M, D;
	static int ans=-1;
	static int[][] graph;
	static ArrayList<Integer> archers=new ArrayList<>();
	static boolean[] check;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt(); 
		M=sc.nextInt();
		D=sc.nextInt();
		graph=new int[N][M];
		check=new boolean[M];
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				graph[i][j]=sc.nextInt();
			}
		}
		dfs(0,0,archers);
		System.out.println(ans);
	}
	
	public static int calDist(int i, int j, int location) {
		return Math.abs(i-N)+Math.abs(j-location);
	}
	
	public static void dfs(int cnt, int idx, ArrayList<Integer> ar) {
		if (cnt==3) {
			int kill=0;
			int[][] temp=new int[N][];
			ArrayList<ArrayList<Enemy>> dist=new ArrayList<ArrayList<Enemy>>(3);
			for (int i=0; i<graph.length; i++) {
				temp[i]=Arrays.copyOf(graph[i], graph[i].length);
			}
			for (int i=0; i<3; i++) {
				dist.add(new ArrayList<Enemy>());
			}
			while (true) {
				for (int i=0; i<N; i++) {
					for (int j=0; j<M; j++) {
						if (temp[i][j]==1) {
							for (int k=0; k<3; k++) {
								int distance=calDist(i,j,ar.get(k));
								if (distance<=D) {
									dist.get(k).add(new Enemy(i,j,distance));
								}
							}
						}
					}
				}
				for (int i=0; i<3; i++) {
					Collections.sort(dist.get(i));
					if (dist.get(i).size()>0) {
						int y=dist.get(i).get(0).r;
						int x=dist.get(i).get(0).c;
						if (temp[y][x]!=0) {
							temp[y][x]=0;
							kill++;
						}
						dist.get(i).clear();
					}
				}
				boolean isEnd=true;		//옮기고 
				int[][] change=new int[N][M];
				for (int i=0; i<N; i++) {
					for (int j=0; j<M; j++) {
						if (temp[i][j]==1) {
							if (i<N-1) {
								isEnd=false;
								change[i+1][j]=1;
							}
						}
					}
				}
				if (isEnd)
					break;
				for (int i=0; i<N; i++) {
					for (int j=0; j<M; j++) {
							temp[i][j]=change[i][j];
					}
				}
			}
			ans=Math.max(ans,kill);
			return;
		}
		for (int i=idx; i<M; i++) {
			if (check[i])
				continue;
			check[i]=true;
			ar.add(i);
			dfs(cnt+1,i,ar);
			check[i]=false;
			ar.remove(ar.size()-1);
		}
	}
	
	public static class Enemy implements Comparable<Enemy>{
		int r; 
		int c;
		int d;
		Enemy(int r, int c, int d) {
			this.r=r;
			this.c=c;
			this.d=d;
		}
		@Override
		public int compareTo(Enemy o) {
			if (o.d==this.d) 
				return this.c>=o.c?1:-1;
			else
				return this.d>=o.d?1:-1;
		}	
	}
}

이것 역시 간결하게 풀지 못한 것 같다. 

 

dfs로 있을 수 있는 경우의 수를 구한다->원본인 graph와 똑같은 temp 배열을 만든다->graph를 돌면서 적의 거리와 궁수의 거리를 계산한 뒤 각각 arraylist에 넣는다->arraylist sort 후 제일 먼저 나온 값(=물리칠 적)에 대해 0을 써준다->적을 옮긴다(이때 change라는 임시 배열 만들어서 값 옮겨준 뒤 다시 change 값을 temp에 넣어준다)

 

인데.. 메모리 낭비가 심하다.

우선 적의 거리와 궁수의 거리를 계산한 걸 arraylist에 넣어줘서 나중에 sort를 하는 방식보다는 그때그때 값을 비교해줘서 최소값을 선정해주는게 베스트다. min값을 설정하고, 거리가 같을 경우에는 minC를 비교하는 식으로 진행한다.

 

그리고 visited 배열을 만들어서 처리할 적의 위치를 표시한 후 graph에 그 위치에 0을 써주면 된다.

성 바로 위에 행은 모두 0으로 표시해서  성이 있는 칸으로 이동한 경우에는 게임에서 제외된다는 조건을 구현하자.

그리고 "이동을 어떻게 효율적으로 할 것인가?"가 큰 고민거리였는데, N-1번째 행부터 시작해서 0번째 행까지 그 바로 위에 있는 행에 있는 값들을 써주면 값 손실 없이 잘 옮겨질 수 있다. 

다른 case를 돌 때 graph의 값을 따로 저장한 temp 를 이용해 다시 graph를 원상복귀 시켜준다.

있을 수 있는 최대 턴은 N이 된다. 그래서 while 대신 for을 쓸 수 있다.

 

https://steady-coding.tistory.com/34