SWEA - 벽돌깨기 java

중간에 있는 벽돌이 깨졌을때 없어지는 구현을 자동적으로 처리하기위해 list를 이용했다. 

계속 값복사를 해줘야해서 불편하긴함

 

 

package a0405;

import java.util.*;
import java.io.*;

/*
 구슬 개수만큼 던질때 최대한 벽돌을 많이 부셔야됨 
 -> 구슬개수만큼 중복순열 돌리면 될듯?
 
 1) 구슬 놓는다 
 2) 놓는 위치에 따라 영향 미치는 범위를 다 체크 
 3) 체크한 범위를 다 0으로 바꾸고 다음 중복순열로 돌림 
 4) 구슬 개수만큼 중복순열 돌리면 없어진 벽돌수 체크 -> 최대값 갱신 
 
 구슬 영향범위에 따라 없어지는 부분 list로 하면 편할듯?
 
 */

public class 벽돌깨기 {

	static int ballnum;
	static int sero;
	static int garo;
	static int firstnum = 0;
	
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			
			StringTokenizer ST = new StringTokenizer(br.readLine());
			
			ballnum = Integer.parseInt(ST.nextToken());
			garo = Integer.parseInt(ST.nextToken());
			sero = Integer.parseInt(ST.nextToken());
			firstnum = 0;
			minnum = Integer.MAX_VALUE;
			
			int[][] arr = new int[sero][garo];
			for(int i=0; i<sero; i++) {
				ST = new StringTokenizer(br.readLine());
				for(int j=0; j<garo; j++) {
					arr[i][j] = Integer.parseInt(ST.nextToken());
					if(arr[i][j]>0)firstnum++;
				}
			}
			
			ArrayList<ArrayList<Integer>> list = new ArrayList<>();		//삭제과정 편하게 하려고 list로 복사 
			
			for(int i=0; i<garo; i++) {
				list.add(new ArrayList<>());
				for(int j=sero-1; j>=0; j--) {
					if(arr[j][i]==0)continue;
					list.get(i).add(arr[j][i]);
				}
			}
			
			permutation(0, list);
			System.out.println("#"+t+" "+minnum);
		}
	}
	
	static int remaincnt(ArrayList<ArrayList<Integer>>list) {
		int cnt = 0;
		//System.out.println("체크시작");
		for(int i=0; i<list.size(); i++) {
			for(int j=0; j<list.get(i).size(); j++) {
				//System.out.print(list.get(i).get(j)+" ");
				if(list.get(i).get(j)!=0)cnt++;
			}
			//System.out.println();
		}
		//System.out.println("cnt:"+cnt);
		return cnt;
	}
	
	static int minnum;
	
	static void permutation(int cnt, ArrayList<ArrayList<Integer>>list) {
		
		if(cnt == ballnum) {
			//기존 벽돌개수 - 남은개수 = 사라진 개수
			int remain = remaincnt(list);
			minnum = Math.min(remain, minnum);
			return;
		}
		
		ArrayList<ArrayList<Integer>> copylist = new ArrayList<>();	//list복사
		for(int i=0; i<list.size(); i++) {
			copylist.add(new ArrayList<>());
			for(int j=0; j<list.get(i).size(); j++) {
				copylist.get(i).add(list.get(i).get(j));
			}
		}
		
		for(int i=0; i<garo; i++) {
			permutation(cnt+1, throwball(i, copylist));
		}
	}
	
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static ArrayList<ArrayList<Integer>> throwball(int idx, ArrayList<ArrayList<Integer>>list) {
		
		ArrayList<ArrayList<Integer>> copylist = new ArrayList<>();	//list복사
		for(int i=0; i<list.size(); i++) {
			copylist.add(new ArrayList<>());
			for(int j=0; j<list.get(i).size(); j++) {
				copylist.get(i).add(list.get(i).get(j));
			}
		}
		
		int throwi = idx;
		
		int throwj = copylist.get(idx).size()-1;
		if(copylist.get(idx).size()==0)return copylist;
		
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {throwi, throwj});
		int[][] visit = new int[garo][sero];
		visit[throwi][throwj] = 1;
		
		while(!q.isEmpty()) {
			int now[] = q.poll();
			int nowi = now[0];	int nowj = now[1];
			int len = copylist.get(nowi).get(nowj)-1;
			//System.out.println("idx:"+idx+" nowi:"+nowi+" nowj:"+nowj+" len:"+len);
			for(int d=0; d<4; d++) {
				for(int l=1; l<=len; l++) {
					int ni = nowi+di[d]*l;
					int nj = nowj+dj[d]*l;
					
					if(check(ni, nj, copylist) && visit[ni][nj]==0) {
						visit[ni][nj] = 1;
						q.add(new int[] {ni, nj});
					}
				}
			}
		}
		
		for(int i=garo-1; i>=0; i--) {
			for(int j=sero-1; j>=0; j--) {
				if(visit[i][j]==1)copylist.get(i).remove(j);
				//System.out.print("remove!!"+" i:"+i+" j:"+j);
			}
		}	
		
		return copylist;
	}
	
	static boolean check(int i, int j, ArrayList<ArrayList<Integer>>list) {
		if(0<=i&&i<list.size() && 0<=j&&j<list.get(i).size())return true;
		return false;
	}
}