14502 연구소

코드 

import java.util.ArrayList;
import java.util.Scanner;

class Main {
	
	static int a[][];
	static int copy_a[][];
	static int N,M;
	static int max_zero=0;
	
	// 사방 탐색용 배열 
	//                 동 북 서 남
	static int row[] = {0,-1,0,1};
	static int col[] = {-1,0,1,0};

	static class Dot {
		int x;
		int y;
		public Dot(int x,int y){
			this.x= x;
			this.y= y;
		}
	}
	static ArrayList<Dot> virusList =new ArrayList<>();
	static ArrayList<Dot> safeList =new ArrayList<>();
	static void spreadvirus(int dx, int dy) {
	
			for (int i = 0; i < 4; i++) {
				int x= dx+ row[i];
				int y= dy+ col[i];
				if(x<0 ||y<0 ||x>=copy_a.length || y>=copy_a[0].length )continue; //넘어가면 패스 
				if(copy_a[x][y]==0) {
					copy_a[x][y]=2; //감염
					spreadvirus(x,y);
				}
			}
		}
	
	public static void zero_loop(int level,int start) {
		if(level ==3) {
			
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[0].length; j++) {
					copy_a[i][j]=a[i][j];
				}
			} // a를 copy 
			
			// 바이러스 퍼뜨리기
			for (Dot dot : virusList) {
				spreadvirus(dot.x,dot.y);
			} 
			int changed_zero=0;
			
			//	0 갯수 세기 max 
			for (Dot dot : safeList) {
				
				if(copy_a[dot.x][dot.y]!=0) {
					changed_zero++; // 감염되서 2가되거나, 벽이된 0 갯수는 changed_zero
				}
			}
			max_zero=Math.max(max_zero, safeList.size()-changed_zero);
			
			return;
		} // 0 을 3개 선택  for
		
		for (int i = start; i < safeList.size(); i++) {
			
			a[safeList.get(i).x][safeList.get(i).y]=1;
			zero_loop(level+1,i+1);
			a[safeList.get(i).x][safeList.get(i).y]=0;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		a =new int[N][M];
		copy_a=new int[N][M];
		
	
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[0].length; j++) {
				a[i][j]=sc.nextInt();
			}
		} 
		//2의 좌표를 virusList에 저장, 0 의 좌표도 zero_List에 저장
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[0].length; j++) {
				if(a[i][j]==2) {
					virusList.add(new Dot(i,j));
				
				}else if(a[i][j]==0) {
					safeList.add(new Dot(i,j));

				}
			}
		}
		
		//3개 벽 골라서  max 값 추출 
		zero_loop(0,0);
		
		System.out.println(max_zero);
		
		
	}

}

 

 

중복 제외 하는법 :  

ex) 중복 제외 3개를 고를때 첫번쨰 i ~ 부터 for문 

두번째 i+1  부터 for문 

세번째 i+2  부터 for문을 돌리면 겹치지 않고 모든 경우의 수를 다 탐색 할수있다.  

 

포인트는 32번째 줄에서 3개를 1로 만들고 바이러스 갯수를 세었다면, 다시 0으로 만들어 주는 것이다. 

아래코드는 위 코드 중 zero_loop 메소드 코드인데, 

바이러스 3개를 뽑고 0 갯수 세는 것을 재귀로 DFS 를 구현하였다. 

public static void zero_loop(int level,int start) {
		if(level ==3) {
			
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[0].length; j++) {
					copy_a[i][j]=a[i][j];
				}
			} // a를 copy 
			
			// 바이러스 퍼뜨리기
			for (Dot dot : virusList) {
				spreadvirus(dot.x,dot.y);
			} 
			int changed_zero=0;
			
			//	0 갯수 세기 max 
			for (Dot dot : safeList) {
				
				if(copy_a[dot.x][dot.y]!=0) {
					changed_zero++; // 감염되서 2가되거나, 벽이된 0 갯수는 changed_zero
				}
			}
			max_zero=Math.max(max_zero, safeList.size()-changed_zero);
			
			return;
		} // 0 을 3개 선택  for
		
		for (int i = start; i < safeList.size(); i++) {
			
			a[safeList.get(i).x][safeList.get(i).y]=1;
			zero_loop(level+1,i+1);
			a[safeList.get(i).x][safeList.get(i).y]=0;
		}
	}

 

처음에  나는 바이러스리스트를 스택으로 만들었는데 , 순차적으로 루프 1번만 돌거라서 배열에 저장해놓기만 하면 되었다. Dot 클래스 를 만들어서 좌표(x,y) 로 나누고, 

arrayList 를 써서 for each 문으로 돌렸다.

//Dot 클래스 만들기
static class Dot {
		int x;
		int y;
		public Dot(int x,int y){
			this.x= x;
			this.y= y;
		}
	}

 

코딩테스트에는 arrayList > array 

 

arrayList보다 array 로 구현한것이 시간,메모리 측면에서 효율적이다.

0 인 부분 좌표의 배열을 만들어서

2로 바뀌었는지 비교를 해가며, 0의 갯수를 세었다. 

0 좌표를 만들때 array(배열) 로 했었는데 코딩하는데 [index][0]=x, [index][1]=y 이런식으로 넣다보니 코딩이 오래걸려서 더효율적인 방법을 찾다가 다른 사람은 좌표클래스Dot 이랑 arrayList 로 간단하게 짜서

내거를 arrayList 로 짜보고,

원래 내 것(array)와 비교를 해봤다.  결과는 예상대로 arrayList가 더 오래걸린다. arraylist 클래스 자체를 불러오는데 가져올 클래스가 많아서 그런 것 같다. 근데, 프로그래밍 대회가 아니라면 , arrayList로 짜는 것이 코딩하는데 오랜시간이 안걸려서 좋다.  

 

결론

프로그래밍대회 -> array 로 짜기  why?: 시간과 메모리를 아낄수있으니까!

코딩테스트 ->arrayList로 짜기 why? : 코딩하는 시간을 단축할 수있다.