17375: 캐슬디펜스

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

17135번: 캐슬 디펜스

1. M칸중에 궁수자리 3개뽑기 = mC3

2.0~M-1까지 배열생성 => 조합의 재료

3. 0~M-1중에서 3개뽑아서 조합생성 -> result에 저장

4. map :: 맨마지막줄 result인덱스에 궁수(2)저장

5. allZero가 될때까지 attack,move반복

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_17135_유동훈 
{
	static int[] result;	//조합 결과저장
	static int N;
	static int M;
	static int D;
	static int[] input;	//0~M-1 까지 조합만들 경우의수 저장
	static int[][] map;	//적=1번, 궁수=2번
	static int[][] origin;
	static int answer;
	static int count;	//제거한 적숫자
	
	/*
	 * depth=현재까지 뽑은 원소수
	 * start=조합시도할 원소의 시작인덱스
	 */

	static void print()
	{
		for(int i=0;i<N+1;++i)
		{
			//st= new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				//map[i][j]=Integer.parseInt(st.nextToken());
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
	
	/*
	 * 깊이, 시작인덱스, 
	 * 
	 */
	static void comb(int depth, int start)
	{
		int r=result.length;	//뽑을 원소수
		if(depth==r)
		{
			//게임시작!
			copyArray();//맵 원상복구, 초기화
			
			for(int j=0;j<M;++j)	//이전에 들어있던 궁수 지우기
				map[N][j]=0;
			for(int i=0;i<result.length;++i)	//맨 아래칸에 새 조합 궁수 넣기
				map[N][result[i]]=2;
			
			//print();
			//System.out.println("끝");
			
			while(true)
			{
				//print();
				boolean isAllZero=true;
				Loop: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)
						{
							isAllZero=false;
							break Loop;
						}
					}
				}
				if(isAllZero) break;
				attack();
				moveEnemy();
				//print();
			}
			//게임 끝!
			//print();
			//System.out.println("게임 끝!!!!!!!!!!!"+count);
			answer=Math.max(answer, count);
			count=0;
			return;
		}
		
		for(int i=start;i<M;++i)
		{
			result[depth]=input[i];	//depth를 인덱스로 써라
			comb(depth+1, i+1);
			
		}
		
		
	}
	
	static int[] getCloseEnemyPos(int Ax,int Ay,List<int[]> enemyPos)
	{
		int[] result=new int[3];
		int distance=Integer.MAX_VALUE;
		
		//거리가 같거나 짧은놈들 리스트에 담기(X,Y,거리)
		List<int[]> shortEnemy = new ArrayList<>();
		for(int[] item : enemyPos)
		{
			//사거리밖이면 컨틴뉴
			//if(Math.abs(Ax-item[0])+Math.abs(Ay-item[1])>D) continue;
			
			if(distance>=Math.abs(Ax-item[0])+Math.abs(Ay-item[1]))
			{
				distance=Math.abs(Ax-item[0])+Math.abs(Ay-item[1]);
				//if(distance<=D)
				shortEnemy.add(new int[] {item[0],item[1],distance});
			}
		}
		
		//1.거리순 정렬
		//2. 거리가 같다면 y좌표 순 정렬
		if(shortEnemy.size()>1)
		Collections.sort(shortEnemy, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				if(o1[2]==o2[2])	return o1[1]-o2[1];
				return o1[2]-o2[2];
			}
		});
		
		
		result[0]=shortEnemy.get(0)[0];
		result[1]=shortEnemy.get(0)[1];
		result[2]=shortEnemy.get(0)[2];
		
		return result;
		
	}
	static void attack()
	{
		/*
		 * 0.for(archers)
		 * 1.getCloseEnemyPos
		 * 2.map[enemyPos]=0;
		 * 
		 */
		
		//맵순회하며 적좌표저장
		List<int[]> enemyPos=new ArrayList<>();
		for(int i=0;i<N;++i)
		{
			for(int j=0;j<M;++j)
			{
				if(map[i][j]==1)
				{
					enemyPos.add(new int[] {i,j});
				}
			}
		}
		
		//궁수1,2,3과 가장가까운 적들에 대해
		for(int a=0;a<result.length;++a)
		{
			int[] enemyPosFinal=getCloseEnemyPos(N, result[a], enemyPos);
			//
			
			//System.out.println(Arrays.toString(enemyPosFinal));
			//이미 0이다? -> 겹치는놈공격 ->count++안함
			
			if(enemyPosFinal[2]<=D)
			{
				if(map[enemyPosFinal[0]][enemyPosFinal[1]]==0)
				{
					//nothing
				}
				
				//1이다?->최초공격->카운트++ && 0대입 => 적제거표시
				if(map[enemyPosFinal[0]][enemyPosFinal[1]]==1)
				{
					count++;
					map[enemyPosFinal[0]][enemyPosFinal[1]]=0;
				}
			}
			
		}

	}
	
	static void moveEnemy()
	{
		//1.한칸씩 아래로
		//2. 첫줄을 0으로 밀기
		//Stack<Integer> s=new Stack<>();
		int[][]temp =new int[N][M];
		for(int i=0;i<N;++i)
		{
			//st= new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				temp[i][j]=map[i][j];
			}
		}
		
		
		for(int i=1;i<N;++i)
		{
			//st= new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				//int temp=map[i+1][j];	//덮어씌워지는값
				map[i][j]=temp[i-1][j];	//덮어쓰기
				
			}
		}
		//print();
		
		//for(int i=0;i<1;++i)
		{
			//st= new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				map[0][j]=0;
			}
		}
		
	}
	
	static void copyArray()
	{
		for(int i=0;i<N;++i)
		{
			//st= new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				map[i][j]=origin[i][j];
			}
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		//int T= Integer.parseInt(br.readLine());
		st= new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		D=Integer.parseInt(st.nextToken());
		
		origin=new int[N+1][M];	//맨아래칸에 궁수저장
		map=new int[N+1][M];	//맨아래칸에 궁수저장
		for(int i=0;i<N;++i)
		{
			st= new StringTokenizer(br.readLine());
			for(int j=0;j<M;++j)
			{
				origin[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		//입력 끝!
		
		copyArray();
		result=new int[3];	//궁수는 3명
		input=new int[M];	//0~M-1까지 저장. => 조합만들 재료
		for(int i=0;i<input.length;++i)
		{
			input[i]=i;
		}
		comb(0, 0);
		
		
		
		
		result=new int[3];	//궁수 3명뽑음

		System.out.println(answer);
		answer=0;

		
	}

}